Budapest is also a great eastern Euro vibe. Especially the old, Soviet-looking street cars and busses!
What I have learned in a half century of travel is you learn a lot more about a place trying to talk to its citizens than you ever can visiting monuments or museums. Plus you can make some life long friends.
OK, some old trams remain but they have been throughly modernized so that old feeling is basically gone.