Wild guess: Powerslave?

No, not Powerslave either. Had never heard of that one.
Alright then, new hint. This game was a darling of graphics card manufacturers, and has several versions that were packed in with the graphic cards to show off what they were capable of.

Err...Quake? I'm sure the Quake logo was used as the icon though...

It isn't Daggerfall, right?

It is indeed not Quake. I think you're right about the icon being the Quake logo.

No, the icon for that is a skull with a crown (kinda like the box art).
By the way, the game isn't on GOG sadly (Despite many requests). Two of the games with the same engine are though. Also, it's a bit odd, the game isn't listed in wikipedia's article on '1996 in video gaming', despite it definetly being published in 1996.

Um, doesn't really seem to go with the horned skull, but Mechwarrior 2: Mercenaries?

Correct! It is indeed MechWarrior 2: Mercenaries.

Sure, the skull seems a bit odd at first, but try to look at the shin of the mech on the cover:
http://cfw.sarna.net/wiki/images/d/d3/MechWarrior_2_Mercenaries.jpg?timestamp=20100405015625

It is the sign of the mercenary team Hansen's Roughriders, who train you in the tutorial:
http://cfw.sarna.net/wiki/images/f/fd/HansesRoughridersOriginalCrest.jpg?timestamp=20130826181545

I actually figured my avatar and title would tip my hand, but oh well.

Your turn!

Cool! I just looked at 3dfx enabled games from 1996, thought back to what was popular and compared against that 1996 in Gaming wikipedia list :)

Ok, next one:

Nice one. I just can't remember the name right. "Rusty buggy" maybe?

Not even close, sorry. The game name is just 1 word.

Pressure ?

Oh, right. Now I remember, It is "Pressure".
"Rusty Buggy" was one of the cards you get for this game.

Correct, your turn!

Here's the next one...

Evo Explores?