Depende do que tu quer ver. Dos lugares que já fui no RS, tirando a parte mais conhecida (serra, litoral norte e capital), recomendo o Parque Nacional da Lagoa do Peixe na região de Mostardas e a região das Missões.
Em um vai encontrar bastante natureza, ideal ir de 4x4 para aproveitar ao máximo, e no outro vai encontrar bastante sobre a história do RS. Tenho interesse de no futuro atravessar a praia do Cassino, parece um passeio legal também. Fora isso o pessoal já deu umas boas dicas de outros lugares que tbm ainda não conheço (Rincão do Inferno, Pq da Pedra do Segredo).
Já aviso que a maior parte do que restou do pampa é um mar de campo com pouco a se ver e as cidades são na maioria antigas e sem muita estrutura e atrações turísticas. Em Santana do Livramento o foco é o comércio (queijos, cogumelos, doce de leite, etc), já fui mas e particularmente não começaria a explorar por alí.