どんなものを食べたいのかにもよりますが

ポルトガルというと、やはりお薦めはシーフード、特にタコやアンコウのリゾットがよいと思います。
まず１番目は、そんなに高くなくそれなりに美味しいということで一番無難なのは、COCTEAUさんも薦めておられるテージョ川対岸のカシーリャスです。フェリー（片道プリペイドカードだと1.2ユーロ、20分おきに遅くまで運航）が着く港の周辺に庶民的なシーフードレストランが集まっています。
個人的には、フェリーが到着する港のすぐ右手前方にあるFarolという店（水曜日定休）をお薦めします。ここのお薦めは、ポルトガル北部特産の微発泡性白ワイン Vinho Verde の樽生新酒が飲めることと、タコのリゾット（Arroz de Pulvo）やアンコウのリゾット（Arroz de Tamboril）を１人前でも頼めることです。ちなみに先々月にも行きましたが、量は食べきれないほど多くはなかったです。ただし、料金的には港から離れるほど安くなる感じではあります。
２番目ですが、リスボンで割と時間があり、かつ魚が特にお好きでしたら、バスで１時間ほどのセトゥーバルに行かれることをお薦めします。ここの市場（いろいろな魚がいてなかなか面白いです）の前の海岸線の通りを西に行くと、レストランが何軒か集まっており、そのうちの１軒“O Mamuel”という店に先々月入ったのですが、ここで食べた黒いタチウオのグリルはこれまで海外で食べた魚の中で最も美味しかったです。なお、この黒いタチウオはこの地方の特産だそうです（他では実際にあまり目にすることはありません）。見どころはそんなに多くはないですが、旧市街の町歩きなども楽しめるので、時間があるようなら（そして魚がお好きなら）是非お薦めします。
３番目は少々高級なお店になりますが、リスボンのバイロアルト地区にあるLisboa Noiteというお店です。ここはかつてはファドを聞かせる店だったのですが、2003年にスタイリッシュなレストランに転身しました。ここも先々月、改装以来初めて行ったのですが、とても美味しかったです。また、日本語を流暢に話すイケメンのウエイターがいますので、その点からも１人でいくのには良いかもしれません。ただし、値段はやや高く、私が妻と２人で行った際は、２人で15,000円くらいしました。
あとはCOCTESUさんお薦めのBonjardimのチキンも美味しいですし、ビールがお好きならビール会社サグレスが経営するTrindade（ほとんどのガイドブックに載っている）もお薦めです。それから、ポルトガルにはかつての植民地だつたゴア出身のインド人も多くいるので、インド料理なども比較的安くておいしいと思います。