I returned a short while ago from Portugal, back to Sweden were I live.
For the banknote interested I can recommend visiting two fairs in Lisbon.
First the "thiefs market", (feira da ladra) were I many times have done some good finds in paper money (mostly modern portuguese and colonial types).
The second is a real treasure trove (the market that is called, Mercado da Ribeira.
There you can find every sunday, lots of dealers with the most fantastic and difficult to find coins and banknotes (some that is hard or impossible to find on eBay). One of the bonuses, is that I was able to meet some major players from ebay "live", and also some IBNS members.
Also a nice thing worth recommending is that after the market, you can easily take a local train to the beach a have a swim.
As I am member in the eurotracer program, I was also able to note some interesting info. about the portuguese euro banknotes.
First, that even in Portugal, there are a high proportion of banknotes from other euro emitting countries. Portuguese euro banknotes are some of the hardest to find I think, even harder than Luxemburg in some denominations.
Second, that the new President of ECB, Jean-Claude Trichet, is beginning to appear on a few portuguese banknotes, mostly on the 5 euro banknotes.
The third and most interesting, is that some (a tiny amount?) of the portuguese
euro banknotes are actually not made in Portugal (but still with the portuguese M prefix). I have found two 5 euro banknotes that were made in France and one 20 euro that was made by De La Rue, Gateshead, United Kingdom.