Como bom sulista, vou dar meus pitacos (e sem puxar a sardinha para ninguém =P )
O interior do Paraná tem vários lugares bacanas. O
Cânion do Guartelá (o maior do Brasil), o
Parque de Vila Velha (esses dois são bem próximos um do outro), turismo rural (tem bastante na região oeste do estado, onde minha família mora), além de Foz do Iguaçu, obviamente.
Curitiba é uma cidade que eu acho bastante bacanuda pra conhecer, e dá para emendar a Serra do Mar.
Descer de trem de Curitiba à Morretes/Paranaguá é deslumbrante. E ainda tem a
Ilha do Mel ali pertim, que é linda. Pena que o litoral não seja grandes coisas. Mas essa opção também depende da época do ano que vocês pretendem viajar.
Santa Catarina eu conheço pouco para indicar, mas um lugar que todo mundo recomenda (e que ainda não conheço) é a
Serra do Rio do Rastro. A visão é fantástica, e para quem curte um frio é uma opção muito legal no inverno. Falando em inverno também tem
São Joaquim. Das praias nem precisa falar nada né?
Se curtem parques temáticos, tem tb o Beto Carrero World, que fica ali junto com as praias.
Ah, ainda tem outra opção bacanuda em outubro: a
Oktoberfest de Blumenau!
No Rio Grande do Sul tem várias opções também.
Canela e Gramado são lindas. Inclusive em agosto tem o
Festival de Cinema de Gramado. O
Vale dos Vinhedos também é um percurso bem legal para se visitar e degustar bons vinhos.
E para ajudar mais um pouco, alguns sites governamentais bacanas, com várias informações e links:
Secretaria de Turismo do PR
Santa Catarina Turismo
Secretaria de Turismo do RS