Choosing one of four characters- cursed king Leo, martial artist Mai Ling, noted sorcerologist Tessa or high-tech ninja Kenji- you fight a series of battles against boss monsters (that, critically, you can never play as- a bit like the first Fatal Fury or Street Fighter) who have much larger healthbars than you. During each battle, you'll gain experience points from dropping items (there's food items too) and level-up, which is where the light RPG bits come in- levelling up gives you new attacks and increase your resistance to certain kinds of attack. After either finishing the game or losing, you're given a password (a long one at that) so you can save your current level- it won't make beating the game easier though, as the bosses also get stronger on successive playthroughs, with longer health bars. The AI is pretty tough, but continuing doesn't fully restore their health, so even a low-level player (like me!) can finish the game eventually.
It's a really interesting way to structure a fighting game, but the two-player game is hurt as a result- you can only use the standard four characters, although you can use your password to pit your raised character against your friend- and the hardware the game was on, Capcom Play System III, was notoriously fragile and expensive, so the game apparently wasn't much of a success. It's the only game on the hardware to never get a home port, but is emulated in MAME these days, so it is absolutely worth a try if you'd like to try a boss-rush game disguised as a one-on-one fighter! A lot of the appeal is also in the characters, who are all lavishly animated (and Tessa, who also fights with her cats Al and Ivan hiding hin her trousers, is one of my favourite Capcom characters- fortunately she went on to appear in Pocket Fighter and SVC Chaos after this).
If you'd like to read up more on the game, the Capcom Database page has a lot of character information, and Arcade Quartermaster's shrine to the game is very extensive! (His site uses frames so I can't directly link- Red Earth's page is on the sidebar).
After the cut, a little gallery of the player and boss characters!
Many characters were renamed between Red Earth and Warzard, so English names first, Japanese names second.
Tessa / Tabasa
Mai Ling / Tao
Kenji / Mukuro
A tyrannosaurus rex-like creature with massive horns who can breathe fire. Look at the size of this guy!
Hydron / Nool
A sea creature with tentacles, a sphere and a massive shell. Watch out for freezing attacks!
Ravange / Secmeto
A Sphinx-like robot fused with a lion, ram, dragon and eagle, who just really loves throwing projectiles at you.
Lavia / Luan
A harpy-like creature that also resembles a peacock, and attacks by swooping with her claws.
An oni-like monster, transformed from an ordinary man, Tanuma. Speaks loudly, carries a big club.
A Mayan-style robot that guards the crypt, armed with four swords, and is always the sixth boss.
Although it seems he's the main antagonist, this living suit of armour is just a sub-boss. Can trap your character in a mirror for huge damage.
Scion / Valdoll
A wizard assisted by two dragons, Misery and Despair, who wants to conquer the world. The final boss.