Olá!
"Puxando a brasa à minha sardinha", como sou alentejana reforço a opção Alentejo, interior ou a costa. Bons alojamentos não faltam dependendo do que se pretende gastar.
1ª opção: o interior
Se a ideia é ter sempre algo para fazer, a visita a monumentos históricos (castelos, igrejas, palácios, monumentos megalíticos, etc) é uma boa opção. Então, vindo de Coimbra via Santarém, Coruche, pode começar por Montemor-o-Novo, Évora, que é uma cidade encantadora com muito para ver, Arraiolos, Estremoz, Vila Viçosa (a não perder a visita ao Palácio) e finalmente Elvas. Ou então, se a opção for Marvão e Castelo de Vide, dois lugares lindos, em Estremoz segue direito a Portalegre, uma cidade também muito bonita.
2ª opção: a costa
Vindo de Coimbra, talvez em direção a Lisboa, pode começar por Setúbal, visitar a cidade e as suas praias e a serra da Arrábida que é deslumbrante, seguindo daí para a costa alentejana. Aqui tem duas opções, ou faz a travessia do Sado para Tróia por barco (muito agradável) ou segue direito a Alcácer do Sal.
Na Costa vale a pena sobretudo explorar as maravilhosas praias muito embora, se o tempo não estiver bom e seguro, poderá não ser tão agradável. Em Tróia tem boas opções de alojamento, assim como na Comporta ou em Grândola.
Alguns alojamentos:
Évora:
http://www.imani.pt/
Arraiolos:
http://www.herdadeamendoeira.com/
Montemor-o-Novo
http://www.wonderfulland.com/choracascas/
http://www.moinhodoalamo.com/index.php/pt/
http://www.hoteldaameira.pt/
http://l-andvineyards.com/pt/
Espero ter ajudado