Stayed at the HI Almeida a few weeks ago. Pretty standard drab HI really, got an 'Executive Room' which had slightly better cosmetics and a bath robe. Shoddily built hotel - all the doors were heavy and banged, and could be heard throughout the floor when they did, day and night. Not too far from the subway but a bit far out of town for my liking.

Friends I was there with stayed here - http://www.heritage.pt/heritage_av_liberdade.html - which was excellent by all accounts.