Sounds like you're looking for something romantic but not too formal.
I can't give you the best advice regarding ambience--I think everyone has their own idea of what's suitably romantic, but I can talk a bit about food. I'd say good value for some awesome food right now can be had at:
Niagara Street Cafe
Jamie Kennedy Wine Bar
Senhor Antonio's (Chiado's tapas bar)
Lee
Have not been yet, but I hear that Thuet's revamp (his bistro) is doing wonders for his business.
Kalendar, when I was there many years ago, was fairly ehn. Nothing along that stretch of College St. has ever really impressed me that much. Food's boring and the decor is so-so. That said, I was having lunch on their patio that day.
If you're looking fancy and high-end, there's no limit to where you could eat. As people have noted already: Scaramouche, Perigee, Susur. You could do Canoe, Amuse-Bouche, George, Auberge. If you've got the money, I'd head to Splendido.
