The 16F628-04 is a 4MHz max speed device, should be fine for experimenting. Suprised they still sell it.
As for the Sparkfun programmer you'll have to ask them, but it shouldn't make any difference as long as it's got power before you run its software.
In theory! - there's no way they make seperate chips for different speeds, and no way a 20MHz chip will only work at 4MHz. I've never seen, and never heard of, a 4MHz 628 that doesn't work perfectly well at 20MHz.
I suspect they just take a batch of normal 20MHz devices and label them as 4MHz - it's purely a sales ploy!.
But it's not that much different, and I would expect any software to probably cover the 628 as well - even DOS software - unless it's never been updated at all? (from like 15 years ago?).
Programmers don't 'recognise code' at all, you simply need programmer software that supports the chip you want, on the hardware you have. The 16F84 and 16F628 use identical programmer hardware though, and only slight software differences. If you don't use the correct programmer software, set to use the correct target chip, it won't work.
Ok, the reason I wanted the dos version is I have a very old laptop, windows 3.11 and dos 6. I didn't want to accidentally mess up the new one but since you said laptops won't work I'm not sure what to do. My desktop is a Macintosh.