Happy to hear that you are seriously considering Portugal!
When travelling,I prefer not to spend a lot of money just for a bed,but of course I stick to clean and decent places. In Portugal,accomodation is less expensive than in most european countries;for a double in a good 3-star hotel count about 50-70 euros in the countryside and 70-90 in Lisbon and Porto(the only real big cities). In Lisbon we always stayed in modern chain hotels like Holiday Inn or Novotel,where you know what you'll find;especially Novotel is almost centrally located and quite pleasant.You can surely find advise on more european places from other members.
Outside Lisbon,and assuming that you will drive a car(this is the only way of travelling I would consider,indeed),I usually stay in the countryside,and tour the surrounding towns and attractions during the day.I suggest you have a look at this site:
This is a reservation service for a group of privately owned properties,each being supervised or directly run by the family that owns the house.They have 17th to early 20th century country homes,manors,and city palaces each with a distinct flavour.Tha majority of locations are in the northern half of the country. They offer bed and breakfast in a beautiful setting,in the price range I mentioned above. Their office is located in Ponte da Lima,in the lush Minho region that you mentioned(but you can inquire and reserve online,and pay by credit card).
A place that is not in this site,but is really good(and slightly more expensive),is Quinta da Ferraria in Ribeira de Sao Joao,Rio Maior. It consists of a series of buildings that used to be stables,and a central one with a beautiful lawn and pool.They serve great dinners,too,a very refined home-style food that's worth every cent(about 15 euros).They have horses and bikes.It's near Santarem and not far from Obidos,Tomar,Fatima...
One of the gratest memories from our last vacation(1998)is listening to a Fado concert in the open air,in the center of Evora,on a warm summer night.This music is very traditional,and although I'm an enthusiast of american music(folk,country,bluegrass,blues),I like it so much!,I find fado is a perfect emblem of Portugal.Somehow I find it to be what Neapolitan music is to Italy,something I spontaneously love,even if the rest of italian music is out of my field.The role of the voice and that of the portuguese guitar(one that you cannot forget,after the first time you hear it)melt together in a splendid way.The standard stories are of great sadness(saudade).In other words,portuguese blues. Misia is a young singer,whose mother is portuguese and father catalan(or the other way round?).She reinvented fado in a very sophisticated way;her albumGarras dos sentidos(Erato) contains songs on text from all the major portuguese poets of our century(available on amazon.com and other online record shops).For traditional fado,try to find some recording by Alfredo Marceneiro.A source of information is the site of the main portuguese record label http://www.valentim.pt .
If you need more assistance on specific destinations,let me know!