TftD is probably a very nice game, but I think I'd rather get the original first ;) Thanks all the same.
Will tell you what made an impact, though.
Europa Universalis 2
I had never imagined I'd be into this kind of game; didn't even like the thing when I tried it the first time, went right back to Medieval: TW. But, for some inscrutable reason, it stayed with me, always there in my periphery, teasing me. I've tried numerous games and discarded them, never finished. It wasn't a matter of them being too hard, but rather just not being compelling enough; good games, too. But this thing, this thing I'd never even understood, never given it a real chance, and subconsciously it kept on reminding me. So, upon finding myself suitably bored and not blessed by a sufficiently 3D-capable rig, I decided to give it a second go. It took a bit of reading and forum investigation, but curiously enough, that only heightened my interest. There was meat behind this clumsy declare-invade-besiege-take-rinse-repeat-haggle-profit! mechanism. I am still fascinated how much fun can be had in a game without any meaningful victory conditions, story, progression, characters. In a sense, it was one of the ultimate role-playing experiences: you can mould your state as you see fit, but you have to co-exist with the rest of the world.
Needless to say, it was a profound eye-opening experience. And while I now love the entire grand-strategy genre, I've not yet found a game that's quite as good as good old EU2.