Bloodrayne. This game REALLY surprised me by how much I've been enjoying it.
UFO: Aftermath. 'nuff said.
Dawn of War. I actually picked first one after I got company of heroes. The day it came into my mailbox... Well, I'm playing it since, CoH lies forgotten somewhere in the back.

Hearts of Iron 2: Found it crazy when I played the demo but began to love it
Mount and Blade: Tried it as a demo and thought it looked like a budget game. Then I got hooked
Combat Mission 2: Babrossa to berlin-picked it up for $2, left it, played it last night and it was Close COmbat all over again
Sam and Max: I had heard these games were great, but Sam and Max truly introduced me to adventure gaming
EU3-Same with this one
Crimson Skies-Picked it up for $5 but likd it a lot
Ghostmaster: For $2, I have never seen a better game
Really? I found DoW a gimmicky clone of WC3 with a pathetic cover system. CoH perfected that cover system and I still think it's one of the best modern RTS games (along with WiC)

You realise you have angered the great Warhammer god. His preachers will be along soon to tell you Warcraft was copied from Warhammer and Starcraft was copied from Warhammer 40k

Killing Floor: It looked like yet another stupid zombie game but Steam had a free weekend so I thought what the hell. Best FPS I've played since Quake 3 Arena... and I don't like zombies.
KoTOR: What are the odds of someone making a good RPG in the Star Wars universe? I've loved Star Wars since I was a little kid but even Lucas can't get it right anymore. Let's just say Bioware earned my respect.
UT3: I respect UT2004 but don't care for the gameplay changes over UT. UT3 has a reputation as a consolized mess. That may or may not be true, but it feels more Quakey to me which I really like.

Gothic 1 - I wasn't expecting anything, but despite the awful user interface and fighting system, I fell for it.
E.V.E online - One of the best mmo, imo.
Ryzom - Interesting mmo. I love its unique atmosphere (fauna, flora, tradeskills, everything !).

Mount and Blade: I thought it would suck...thankfully I got it for 5 bucks since I can not stop playing it.
Torchlight: Never played Diablo or Fate, thought this would be a shitty version of Sacred....I was wrong...and got it today for 10 bucks!!! WOOT!!!
Audiosurf: Metallica's Master of Puppets while driving under psychedelic tunnels and lights made my day.
I can go on, but I wont for the sake of bandwidth.

Let them smite me down. CoH is the finest thing to come out of Relic (yes, it even beats Homeworld)

You, good sir, are a blasphemer.
Nothing can touch Homeworld 1 and 2. ( YOU HEAR THAT GOG?! GET THEM GAMES TO US ! )
That being said, I really didn't feel like Warhammer 40k DoW and WC3 were similar at all.
WC3 was half-RPG half RTS, whereas DoW was more focused on strategy imho. I liked both games but they have a very different feel to it. The campaigns were very different too.
Now as far as my list goes:
Space Rangers 2: Rise of the Dominators / Reboot - The game has the worst possible name. The worst possible cover, yet is the most ingenius game released in recent memories. I got hooked and played it for days no end. Truly magnificent. Came in with 0 expectations and was thoroughly blown away.
Risen - After the horrible Gothic 3 and Gothic 3 Forsaken gods, I had lost faith in piranha bytes. Gave the demo a try and .. wow, not as good as Gothic 1 and 2 of course, but still loads better than Gothic 3. note: I wouldn't say that I love it, but I really appreciate it. Considering i had next to no expectations of it being any good, I feel it belongs on this list.
Mount & Blade - I've read reviews but they didn't all sound appealing. It sounded like some sort of budget production fantasy game where you are a hero that can go around doing quests and that you can ride on a horse and recruit some troops thrown in as a gimmic. Boy was I wrong. This is probably the most accurate ( and fun ) medieval war simulator available. Granted, a very niche genre but still, extremely fun.

BioWare didn't even make KotoR 2.
Mass Effect still makes my list, but only because I went into it expecting to hate the shooter-style gameplay. Surprisingly, I found myself enjoying that aspect of the game, which made the game a winner.
The Simpsons Movie game. My girlfriend bought it on clearance at Target. Neither of us were expecting much, but it was actually quite hysterical.
Rome: Total War. I'd never played a Total War game. While I was aware of the acclaim, I kept telling myself that there was "no way that it could really have passed the test of time." Suffice to say that I purchased Medieval 2 a month or so later.
Honorable Mention: Sins of a Solar Empire. I thought it would be enjoyable, but I was suddenly losing ENTIRE DAYS to that game.

Commandos 2: The first time I played this game I immediately started to question my purchase. It seemed like an unpolished, pseudo-rts/tactics game with a lot of little gimmicks thrown in. Wow, was I ever wrong. After getting through the intro missions, I finally started to see the beauty of this game.
Dawn of War 1: When I first tried this game, I thought that throwing out traditional rts template and adding point based resources was a horrible idea. About 3 years later, I tried it again and realized how naive I was before. Its one of my favorite multiplayer games now (great for lan parties!).
Football Manager series: To anyone whos not into football (soccer), this game might look like the most boring thing in the world. But after watching my roommate play it constantly, I knew I had to give it a try. I found that it is probably the most addicting game I've ever owned.
Space Rangers 2: Like previously said, the outward appearance of this game doesn't seem like much, but once you get into it and play it it's extremely fun. I love Sid Meier's Pirates, but after playing this game I don't think I can go back.

Oddly enough, another exception to that rule is the most recent Wolverine game. I was absolutely astounded at how rather good that was. Much better than the utterly naff film. Granted, it was just God of War reskinned, and ludicrously violent but those are all wonderful things :).
Can't think of another two surprises just yet, I'll edit/repost if and when I do.

Die Hard : was expecting a sub-sub-par FPS, but well, it reenacted very well the first movie, with the right voices, the right key-moments. Add to that that i found it very decend visually speaking and okay to control. Really made me think I was John McClane !
Trainz Railroad simulator : Come one, driving a train ??? As a video game ?? WTF, man!! Despite that, I found that game unexpectedly good, relaxing and still challenging at the same time. A good surprise.
Battle Isle : I'm not much in the strategy thing. But then, I fell in love with HoMM and not long after, with the Battle Isle series. Please please please, GOG, next year, bring Battle Isle 1, 2 and 3 to us! It would be an instabuy for me!!

Plants vs. Zombies
Bioshock
Fallout 3

How could you not like PvsZ! It's adorable!
edit:... this is the games you *did* love thread... my bad :\