Yeah, there aren't many Yorkist pretenders worth marrying, and the ones who might possibly be are all male.
There's also the issue of Catherine's dowry to consider as well; Henry VII really didn't want to give that up.
On the other hand, the other big reason for the delay in the remarriage was the fallout between Philip the Handsome and Ferdinand of Aragon; Henry VII had sided with the former, and after Philip died it was tough to mend fences enough to marry in time. Unfortunately Philip's own kids maybe just slightly too young to make a marriage in a hurry (the eldest daughter, Eleanor, mentioned above, was born in 1498), otherwise they would be the logical choice.
Marguerite of Angouleme is the logical French choice, but that requires Henry VII to be willing to switch sides again in the Habsburg-Valois feud.
Henry VII might consider switching sides in the feud, though I don't think Henry VIII would. Henry VIII really dug the old stories of English glory over the French - hence why he fought two wars against them in his reign - so I don't think he'd be keen on a French bride when he would rather regain the lost English possessions from the days of the Hundred Years' War.
As for Eleanor of Austria, yes, she was young, but I still think that many thought her a viable candidate. Henry VIII was young and healthy, and though life was fragile, they likely thought that waiting a couple of years for her to get to a safe age to be a wife and mother was a reasonable gamble. Both Henrys would know very well the story of their (grand)mother, Margaret Beaufort, and how she came to be pregnant with Henry VII. Even at a time when girls becoming mothers at fourteen/fifteen was a normal thing, many were a little horrified at how young she was when Edmund Tudor got her pregnant. So if Eleanor is on a young side (she's seven years Henry VIII's junior), Henry VIII might be willing to wait a couple of years before consummating the marriage.
Though, if Henry VII is worried about the succession, he might be more keen on finding a bride that could start churning out babies sooner rather than later, so you make a good point.
If HVII doesn't arrange something for HVIII before his death, how much of an overriding concern would a foreign dynasty legitamizing marriage choice matter to HVIII?
If he became infatuated with a local talent who played the Anne Boleyn game with him, could he resist it?
I don't know if Henry would fall for that at this age. He's young, and given that his father kept him under lock and key for much of his teenage years, he's probably not had much experience with women and them falling over themselves to be with him yet, so if there's the occasional woman who doesn't appear interested, he'd probably move on. Anne's ploy was used on an older Henry, who was used to women tripping over themselves to fall into bed with him, and who was also madly desperate for an heir. At a younger age, Henry thinks he has all the time in the world to father a son and it's not an enormous concern for him yet.
So Henry might be more keen on a foreign marriage to further England on the international stage - and possibly gain allies for him to hopefully go to war with France at some point. Henry was all about war and glory at that age, perhaps more than he was about marrying and having babies.