I have a blizzard 1230 50MHz. It slows down to the speed of an A500 when I'm running in 256 colours.
Personal paint seems to do a reasnably good job of changing the colours of an image.
You mention Yorkshire scenery. Well, if it's just a field and a couple of houses and sky then it should be fine in 16 colours

(joke)
Does anyone know where I could get patterns from, e.g. to use instead of photos? I;m crap at designing my own in WBPattern. :-)