Transport Tycoon comes to mind. Despite being a pretty simple simulation game, I was too young to completely understand it when I began playing. Several years later, I was hooked, and it's certainly up there in the games I have played the most. Today, they even have a multi-platform emulator for it (think ScummVM but for Transport Tycoon) so I can relive all of my memories on the Mac.
Also, Civilization 2 had a pretty horrible learning curve for me. But now I'm a huge fan of the series, especially the latest installment.