Eva reichte Adam im Paradies einen Apfel. Das ist der Paradiesapfel. So bezeichnete man früher auch besonders auffallend rote Äpfel. Das »Paradies« (i-e) hieß aber auch »Paradeis« (e-i).
Paradeiser
Als dann Kolumbus Amerika entdeckt hat, kamen kurz danach viele neue Früchte nach Europa. Unter anderem eine Frucht, die einem Apfel recht ähnlich sah, und auffallend rot war. Also nannte man diese Frucht im Süden des deutschen Sprachraums »Paradeis-Apfel«. Vom Pardeisapfel war es dann nicht weit zum Paradeiser.
Erdäpfel
Zur selben Zeit kam auch eine knollige Frucht nach Europa, die unter der Erde wuchs. Sie sah ebenfalls einem Apfel oder einer Birne ähnlich. Also hieß diese Frucht »Erd-Apfel« bzw. »Grund-Birne«. Die »Grumba« findet man noch im Dialekt des Südburgenlandes, während der Erdapfel sich als Name in ganz Österreich durchsetzte.
Kukuruz
Zeitgleich kam eine dritte Feldfrucht aus Amerika nach Europa. Es ist eine mannshoch wachsende Getreideart, deren Ähren so groß sind, dass man sie Kolben nennt. Sie wurde über Ungarn nach Österreich eingeführt. In Österreich erhielt diese Getreideart daher einen Namen, der auf die Kuruzen, ein in Ungarn lebendes Volk, zurückgeht: Kukuruz. Ich weiß aber nicht, wie weit nach Westen der Name Kukuruz für den Mais verbreitet ist.
Ergänzung Dezember 2021:
Im Atlas der deutschen Alltagssprache ist kürzlich das Ergebnis einer Befragung über die Verbreitung von Tomate/Paradeiser veröffentlicht worden. Da es gut zur Frage passt, ergänze ich es hier.

Quelle
Das Ergebnis hat mich sehr überrascht, weil ich dachte, das Wort wäre in ganz Österreich verbreitet, was wohl falsch ist. Es wird aber nur in Wien, Niederösterreich, dem Burgenland, Teilen der Steiermark (West- und Oststeiermark sowie die östliche Hälfte der Obersteiermark) sowie Teilen Kärntens (Unterkärnten) häufiger verwendet als »Tomate«. Diese Region ist aber dichter besiedelt als die übrigen Gebiete, so dass trotzdem 60% aller Österreicher in einem Gebiet leben, in dem »Paradeiser« die häufigere Variante ist. Tatsächlich verwenden aber deutlich weniger Österreicher dieses Wort, weil sich vielerorts die »Tomate« anschickt, die »Paradeiser« zu überholen, was vor allem daran liegt, dass die älteren Benutzer des Wortes »Paradeiser« langsam aussterben, während die jüngeren Österreicher in ihrem täglichen Medienkonsum (hauptsächlich Internet, aber auch Kabel- und Satelliten-Fernsehen sowie aus Deutschland importierte Zeitschriften) fast ausschließlich mit dem Wort »Tomate« konfrontiert sind. Selbst in Supermärkten wird das Gemüse mittlerweile kaum noch also »Paradeiser« in den Werbebroschüren geführt, sondern fast nur noch als »Tomate«. Es ist also damit zu rechnen, dass dieses Wort in wenigen Jahrzehnten auch in Österreich ausgestorben sein wird (so wie viele andere Begriffe des österreichischen Deutsch).
Auf DiÖ erschien heuer im Juni ebenfalls ein Artikel zu diesem Thema, in dem sehr ausführlich die Frage erörtert wird, wie die Österreicher diese Frucht nennen: Nun sag: Wie hast du’s mit … "Tomaten" und "Paradeiser"?