The licensed tour guides don't like to hear this, but a good tip is to connect up with a student, preferably someone studying to become a tour guide. They're usually bright and energetic, and will love the opportunity to show a foreigner around their city and practice English.

You can buy their lunch and dinner and mutually arrange a 'gratuity' and everybody wins. We did this in Russia and Hungary and it turned out great!

--Grog--