Carebear... sounds like a nice well cared for 172 would fit
your mission. Forget about the year (obviously the newer the better)
just make sure its been well cared for and flown and the avionics
are fairly new and good shape and its been upgraded and so
forth. So don't necessarily be looking for the lowest hours, but
you don't want want that's been used as a trainer either.
You might also consider some sort of Piper Cherokee, although
I think the fixed gear ones are ugly, but they are good planes.

I would not go with a slowdowner, stick with something
mainstream. If you could find a good 180 HP Skyhawk that
would probably be your best bet.

When you start doing regular trips of 500Nm or more you are
going to want something faster.... pluggin along at 110 knots
gets old after a while.