Matthias was unmarried between 1464 to 1476, up until he married Beatrice of Naples, likely because in that time period he was preoccupied with wars all over. An earlier marriage is a possibility though, providing more time to have a heir.
A German or Italian marriage would be the most likely/fun in light of Matthias' western ambitions.
Random possibilities-
-Matthias wanted to marry Hedwig Jagiellon or another daughter of Casimir IV. It was supposed to be as part of a double marriage with Maximilian I marrying another Jagiellon sister to form an alliance against Hussite Bohemia. Apparently the Jagiellons never really forgave the Matthias for usurping Hungary from them though so it never got anywhere.
-Italian marriages are comparatively easy to get. Ippolita Sforza or Eleonora of Naples are options. Both had multiple issue OTL unlike Beatrice and were successful consorts. Despite Eleonora being Beatrice's sister.
-German marriages are surprisingly difficult. The natural place to look is enemies of Frederick III or Maximilian I, but neither the Wittlesbach or the Leopodine Hapsburgs have anyone to spare. For a brief period from 1468-1469 Matthias was considered an imperial ally, so maybe he could sneak the Emperor's sponsorship for a German marriage during that time (like they tried to do with the Polish marriage)