Final Fantasy 8.

First time through, the game teaches players about the draw system, but doesn't mention refinement or carding, both better ways to get magic.

Second time through I didn't draw any magic, and instead only refined items into magic, and I enjoyed the game a lot more. I also paid much more attention to AP and skills, as well as junctioning magic correctly.

All in all, FF8 was a more complex game than previous FF titles, and the first time through I didn't pay close enough attention. I attempted the game again later, because I couldn't just let an FF game go incomplete. The second time through I ended up playing it much more effectively and liking it better than FF6 and FF7. To this day, FF8 is still my favourite FF game, and one of the RPGs that is arguably my favourite.

In the end, there just weren't enough tutorials in the game, a lot of the mechanics required players to dig on their own. If it came out today in the era of massive tutorials, I think that I would have enjoyed it a lot more the first time through.

3 games come to mind instantly.
Phantasy Star online episode 1 & 2 - bought it on GC then sold it to a friend a week later, ended up buying it about 3 months after that and loving it.

Monster Hunter - didnt really get the point at first, played it occasionally but took me a long time to hit the 'ah-ha' moment.

Half life - Remember playing half life on PC when i was about 10 years old (in 2000) and just thought it was another mediocre fps. That was until Half life 2 came out and i finally saw the beauty of the series

ArtStyle: light trax. The first time I played, I didn't know what the frig I was doing.

The second time, I had a golden epiphany with trumpeting cherubs and winged horses. I made that game my bitch.

I didn't like Final Fantasy VII, Demon's Souls and Dragon Age: Origins (to name a few) the first time i played them. Luckily i tried again, cuz first impressions can be misleading, and now love those games passionately :D

It's as much down to memory and reflexes as it is mastering the boost system, and knowing that "switching lanes" slows you down. You may need to fail at a track half a dozen times while learning the fastest route, where the pickups are, where the obstacles will be if you change your boost strategy, etc.

All this contributes to a most satisfying win when it all comes together. Very rarely does a game make we work this hard to beat it, and that's probably why it gets so little attention from gamers (as well as being too casual to know it exists).

Hmm..

Vanquish could count for that as my first playthrough on hard was very frustrating and then I did a second playthrough on easy and really loved that one.

Another one would be Bioshock, I played the demo when the game launched on PS3 and really didn't like it. I picked it up in a Steam sale years after that anyway and played the first section without being too impressed. Then I took a break and came back to the game some month later and couln't stop playing it until I finished it, very good game.

Sad but true. I heard there are people who thought Donkey Kong was a Microsoft IP.

Deus Ex: Human Revoltion. Also Mass Effect and Dragon Age: Origins, most curiously.