Personally I'd go for the secondhand route also.
As said a no.4 should be really easy to get a hold of, for cheap at buy it now prices.
It might be the case that you would have to bid for anything other than four's and five's.
I would buy a good no four for about no more than 25 pounds, a nice heavy smoother.
a no.5 if the same price would make a good roughing plane.
I'd get a nice no.5 1/2 for the main work, I have two, one for shooting with.
To me, a different tool, the no.5 plane seems tippy in comparison.
I really love the no.5 1/2.
I wouldn't be bothered with what iron came with the plane, as long as the sole of it was sound, as in a good thick casting.(which may well narrow your options)
A bit of rust is no issue, and I'd be inclined to look at those first.
Some folk might be put off if the iron was corroded.
I wouldn't buy any plane without a picture of the front and back to show it was nice and chunky. (if the sole has a twist or whatever, then you've got some meat to work with)
The longer the plane, the more concern this is,
I wouldn't buy a long plane that is refurbished and polished.
No chips out of the mouth (another photo of the underside of the plane)
and looking at the cheeks to see if there was any hairline cracks present.
Preferably no cracked totes or knobs, if so, I'd want pics of each cheek to make sure.
Preferably plenty of life left in the iron, but just because most have a full length iron, and another has a bit less, wouldn't be important to me if wanting the heaviest one.
Not looked at the market on the bay to see the prices since the lockdown.
A good rough guide is to see what a no.4 goes for, buy it now price.
Last I looked it was less than 20 squids for one.
Have fun shopping.
Good luck
Tom