It’s true that they tend to me in more touristic locations, however they are in touristic (and some not-so-touristic) locations all over the country. And they don’t have half a dozen ATMs in the center of Lisbon and Porto, they are several hundreds at least. Sadly outnumbering the MB machines by a large margin these days.
They are also plenty at the airports, so you could also change the PIN the next time you fly in or out of the country.
This map isn’t great (it only lists the 100 closest ATMs to the center of the map), but with some panning around you’ll find a bunch of Euronet ATMs all over the country. Just in between Porto and Lisbon I found them in e.g. Coimbra, close to Leiria/Fatima, Figueira da Foz, São Martinho do Porto, Peniche, Ericeira, Nazaré, Torres Vedras, and more. If you live far from the coast or any reasonably sized city, then yes, there might not be on very close.
@megamaster if you shoot me a PM with your location I can see if I can find any Euronet ATMs near you.
@Lucas I believe you can in the Euronet ATMs there as well.