Toeclips will help - if nothing else, they keep your feet in the optimum pedalling position and they also let you pull up a bit as well as pushing down all the time. I use them, mainly for the keeping my foot on the pedal reason.
The Galaxy was a bit of luck. It was a Uni auction, and all the students wanted MTBs, preferably with s'penshun, and in red. They were paying £50 or £60 for bikes that probably cost that new, and were total rust buckets. No one wanted a drop bar touring bike in lilac metallic paint, with white bar tape and a cross bar. My then BF picked it out, measured me against it, and bid - the only bid, £15. The auctioneer knew me, and made little effort to bump the price up further. We pumped up the tyres, and he rode it home (he wanted to be sure brakes and stuff worked). We stripped it down, resprayed it blue and silver, rebuilt it (that's where I learned most of the stuff I know now) and I rode it to Norfolk on my first solo tour.
9 years later and after a period of not being used, it's just been stripped again and powdercoated red, and I've lined the lugs gold, and it's going to look lovely when it's all fixed up again. I wish the BF was still here to see it.
But enough about me... The main thing is to have a bike you're comfortable with, as Roger said. And start off gently and work up the distances. At least if you're also planning sightseeing and stuff you can take days off when you fancy it. A touring holiday, afterall, is meant to be a holiday....