Besides, GTA breaks the fundamental rule.

Never get out of the car.

Yeah, seconding this request.

Even though it's not exactly the same as Interstate, the only thing I can think of that is remotely similar (in tone, at least) is Slipstream 5000. It's a futuristic racing game, but it maintains the story, fighting and semi-open world qualities of Interstate.

Interstate '76 is one of the best games ever, it is absolutely unique, and not many other games compare in its story-telling quality, and certainly no games that involve driving. Cherish it.

With that said, I would recommend TIE Fighter as the only thing that comes close, but I do not suggest buying the version that they have here until they provide the definitive version (supposedly they are working on it?) I would recommend it in the realm of what you are looking for because:

First and foremost, they are vehicle simulation games, rather than arcade-like or controlling a living being (otherwise I MIGHT suggest Giants: Citizen Kabuto, though that is still a bit more arcade-y.) Of course TIE Fighter takes place in 360degree environments and in I-'76 you are tied to the land (even though it is certainly has plenty of Z-axis action/moments!!!)

Second, it is story driven, and each mission has its individual story to accompany it, just like I-'76, and they cumulatively grow the story into an overall story that develops and (sort-of) ends. But those elements in TIE Fighter are not as supreme as in I-'76. The individual story missions, while sensible and well done and do move the plot along, don't DRIVE the story or have as much of an impact on the individual missions or overall story to even close to how I-'76 does them. They simply aren't of the high caliber story-telling that I-'76 is. Don't misunderstand, it is all very good, and TIE Fighter is an excellent game and belongs on a "best of all time" list of games, but it is not I-'76, which belongs near the top of that list.

Driver: San Francisco might fit your bill. It's bit heavy on the modern eye candy, but has a cool "Quantum Leap/Life on Mars" type of story. It does tend to fall into a bit of the sandbox design of complete various random challenges until you unlock the next story mission, but I had a blast with it. Lots of cars, racing, stunts, and movie chases, and you don't get out of the car for any of that GTA nonsense. Just beware, the story isn't as cohesive as I-76, as it involves a weird feature where you can switch into any car on the fly (Quantum Leap style).

Thanks a bunch, guys!

Slipstream looks like an interesting game, I had no idea anything like this existed :P
TIE FIghter is a game I've beaten time and again, and I completely agree - it's one of the best story-driven vehicle simulation games.
Driver: SF is indeed the closest to what I've been looking for :)

Thank you all again! If anyone else has any titles to recommend, I'll appreciate it a lot!

Well TIE Fighter and Driver: San Francisco have already been covered, which is great.

The only one I can think of which has not been listed yet is Crimson Skies (the PC original, not the super arcadey Xbox sequel.

Out of all three games, I think CS's story strikes the closest to Interstate. It has clear rising stakes from mission to mission, some intrigue to keep you guessing who will do what next, and the same amount of humour that Interstate had. Plus everything is stylish and cool as hell..

Considering both Interstate 76 and TIE Fighter were essentially the biggest influences on Crimson Skies (and it shows!) I'd definitely recommend it. It also happens to have the most perfect arcade flight model I've ever seen in a game, in much the same way that the driving physics in the Driver games felt utterly perfect too.

Ooo, I will have to give that a look, thanks for the suggestion!

I'd suggest Mafia. It really was a great combination of driving and shooting, and a great story.

There ares some other games with similar promise:
- Quarantine series
- Driver series
- Zombie Driver
- GearGrinder
- Spy Hunter series
- and there was a futuristic racing/car game for DOS, that title began with Z ... but don't remember it.

But if you are looking for a real story, than yes, outside Driver: San Francisco ... there aren't many.

EDIT: Yeeee, I've got it/found it!
It is called Zone Raiders:
https://www.youtube.com/watch?v=xt-HixevAP8

How about Strike Commander? Just like TIE Fighter, it's not a car driving simulator, but it has a proper story.

Redline. It's also an FPS.