I don't need data, just voice, and quite likely a constant inbound number.
If you don't care where the number originates you can even use a voip.ms number and just forward to the different SIMs as you move around.
Any good options for a phone (eBay, obviously, but other ideas)?
You'll probably pay more for shipping on an eBay purchase than you will for a cheap phone. Last time I was in Portugal I got a phone for my dad to use and it couldn't have been more than $20. You can buy them here for the same price or less from 7-11 via their Speakout pay as you go service.
For that matter, cheap phone recommendations? I assume anything that says "GSM europe" should work?
Any unlocked GSM phone obtained in Canada will work. Or any AT&T GSM phone from the US.