Ну если поцивильнее, то как ни крути, это только Москва и Питер.
В остальных наших городах инфраструктура хромает, и "изнеженных" иностранцев может повергнуть в шок.

Если ж они все-таки не изнеженные:
- города Золотого Кольца - Сергиев Посад, Углич, Владимир, Ростов Великий, Суздаль, Переславль Залесский, Муром, Ярославль (вот тут мне очень понравилось! ), Кострома;
- Новгород Великий;
- Казань (сочетание культуры Европы и Азии);
- Владивосток (наша Япония);
- Петропавловск-Камчатский (сам не был, но все говорят, что там очень красивая природа).
Ну для экзотики можно еще куда-нить на Крайние Севера.

В ЗО и Новогород можно устроить тот самый походно-пешеходный путь. Спокойно ездить из одного городка в другой, останавливаться на пару дней, осматривать достопримечательности и вперед.
Народ там везде приветливый, спокойный. Атмосфера аналогичная.

В Казань и далее можно "оформить" прогулкой по Волге. Соответственно, плюс еще Самара, Нижний Новгород.

Ну а в Азию уже самолетом.