I can't give you too much advice as I'm just starting up with this stuff too but I live in Rome, Italy and I'm planning on using Destinator2 with a custom built carputer.
http://www.destinator.it
It was featured on an Italian newspaper (can't remember which one) and got a good review.
I'm getting a new car next month and I was planning on getting a 'normal' car GPS system but the base price was 1900 Euros. You can build your own (and have fun at it) for less than half of that. Of course if you're not interested in building your own, I'd suggest a getting a PDA as it's still cheaper and buy the desintator kit for it. Also you'll be able to use GPS while walking around the city. I'd love to have that when I'm visiting other cities!
Good luck!