I could have sworn that I'd read that leaves with red or purple undersides are an adaptation by understory-dwelling plants to collect more light. Damned if I can find a source to back me up, though: Google failed me completely. I checked some of my books, too. So maybe that's not true. Most of these do appear to be understory plants, though, whatever the reason for their pigmentation.
Calathea roseopicta 'Medallion.' I think.
Cissus discolor (begonia vine).
Cyanotis kewensis (teddy bear plant).
Excoecaria cochinchinensis (Chinese croton).
Hemigraphis exotica (purple waffle plant).
Nematanthus NOID (guppy plant).
Philodendron hederaceum micans (heart-leaf philodendron).
Selaginella erythropus cv. (red spike moss)
Tradescantia spathacea. (oyster plant, Moses in the cradle)
Making recommendations from this batch of plants is pretty easy, since there are only four plants on the list that I've had good experiences with (Cyanotis, Nematanthus, Philodendron, Tradescantia).
Of those four, Philodendron hederaceum micans is far and away the easiest; it's an adaptable, flexible plant that will survive a fair amount of abuse while still looking good. Tradescantia spathacea is next: it's a perfectly nice plant, and also very tolerant, but it won't develop the purple coloration without a lot of light, so it is demanding on that one point.
Cyanotis kewensis and Nematanthus cvv. are both a little fussy for me: both are usually robust and fast-growing, but both also sometimes die back for no obvious reason, and Nematanthus sometimes abruptly defoliates, which is likely either a cry for more light or a delayed response to drought. Both also need fairly bright light, and not all Nematanthus varieties have the red underside. So those are tied for my third recommendation.
The rest of this field is not very promising.
I've never tried Alpinia luteocarpa, but the ginger family plants I am acquainted with aren't plants I'd necessarily recommend to anybody.2
Calatheas are virtually never a good idea, for anybody, though they're not the worst choice from the list.
I've heard of people keeping a Cissus discolor indoors for any substantial length of time, but I think the people telling those stories are lying.
Excoecaria cochinchinensis and I only just met, so I have no idea what it's like.
I've tried Hemigraphis exotica twice now and will not be buying a third one; they need very intense light to maintain their coloration, plus they can't go dry, even briefly. Since briefly going dry is something that's very likely to happen to a plant that's in intense light, this basically means that you really have to be on the ball with the watering.
And, finally, Selaginella erythropus, which may be the very worst choice possible from this list, unless you plan to put it in a terrarium. In a terrarium, it'll probably do great.
- Several Alocasias have green or gray surfaces with purple undersides, including A. amazonica 'Polly,' A. 'Mayan Mask,' and A. lauterbachiana. They're a bit too attractive to spider mites for my tastes, and 'Mayan Mask' is huge, but it is possible to grow them indoors. (suggested by tay696)
- Many Begonia cvv. have red undersides; B. x erythrophylla, the "beefsteak begonia," has a particularly vivid green-red contrast and is easy to grow.
- Virtually all Calathea varieties have red or purple undersides: C. burle-marxii, C. insignis (rattlesnake plant), C. makoyana (peacock plant), C. ornata, C. roseopicta, C. 'Corona,' C. rotundifolia, and C. rufibarba would all qualify, among several others. The only two I can think of that don't have a contrasting underside are C. concinna and C. zebrina. None are particularly recommended as houseplants, for a number of reasons.
- Some Columnea species / varieties have red undersides; the only one I know of specifically is C. orientandina, and its leaves are only red underneath at the leaf tips. Columneas seem to grow okay for me, though I've only had any since spring; other people appear not to find them terribly difficult. (suggested by allandrewsplants)
- A handful of Euphorbia species have green leaves with red-violet to violet backs: E. millotii, E. pachypodioides, and Synadenium grantii;3 Synadenium's are typically either uniformly green with red flecks or uniformly red-violet, but there are plants out there which are green with a red-violet flush on the undersides of the leaves. I have only grown Synadenium, which is ridiculously easy; I don't know what the other two are like in cultivation. (suggested by Sentient Meat)
- Geogenanthus poeppigii (seersucker plant; formerly G. undatus) has highly textured leaves (texture is similar to Peperomia caperata) which are dark green with silver stripes on top and purple underneath. I don't know what it's like as a houseplant; I don't think I've ever even seen it for sale, but it's in a lot of the books, so people must have grown it once.
- Tahitian bridal veil, Gibasis geniculata, has small green leaves with purple undersides when grown in good light, and is a fairly easy-to-grow, if messy, plant.
- Homalomena 'Purple Sword' has broad leaves, mottled in green and gray, with purple backs and petioles. (It is, for some reason, often sold as an Aglaonema or Schismatoglottis; there doesn't seem to be much consensus on the ID, from what I could find on Google.) I haven't been happy with the Homalomenas I've tried to grow (though 'Emerald Gem' and I did eventually reach an understanding), and I've never seen a Schismatoglottis for sale so I assume they're probably difficult as well. Aglaonema and I get along great, which is a major part of my concluding that the plant in question is probably not an Aglaonema. (suggested by tay696 as Aglaonema)
- Hoya curtisii has small heart-shaped leaves which are marbled green and silver on top and flush brownish-red on the underside in certain conditions. I've never grown one, but assume their care is similar to that for other Hoyas. (suggested by Tigerdawn)
- In bright light, Maranta leuconeura var. erythroneura (prayer plant) leaves will have a red back. The other varieties of M. leuconeura never have red undersides, as far as I know. Not recommended, though people do grow them.
- Monadenium rubellum (sometimes M. montanum var. rubellum) is an unusual caudex-forming succulent. The leaves are green with dark red undersides. I've never seen one for sale or tried to grow it.
- Musa zebrina has large green leaves which are splotched with red above and solid red below. I've never tried to grow this one, either, but I would guess it's probably fairly difficult indoors. They may be grown outdoors during the summer and then brought in to go dormant during the winter.
- Paphiopedilum delenatii and some other Paphiopedilums have reddish-purple backs on the leaves, at least in some conditions. Not recommended for beginners, but growable. (suggested by orchideya in comments)
- Peperomia rugosa has glossy, bumpy, olive green leaves with a red underside. I don't know how it is as a houseplant, but I'm about to find out 'cause I just got one. (I didn't know what it was, or I wouldn't have. I'd been hoping to find out that it was a Begonia with atypically symmetrical leaves.)
- Pereskia aculeata cv. 'Godseffiana's (lemon vine, yellow rose cactus) leaves aren't so much green on top and red underneath as they are yellow on top and hot pink underneath, but I figure it's close enough. I've only had one briefly (since May), but I like it a lot, and all indications are that it's going to be an easy plant.
- Philodendron linnaei is sometimes, but not always, green with a purple underside (possibly light-dependent?). It doesn't seem to be sold very widely, so I have no idea what it's like as a houseplant.
- Philodendron mexicanum has glossy, long green leaves with a red back, and is pretty easy to grow.
- Plectranthus ciliatus (candlestick plant, blue spur flower) develops a purple underside in strong light; I had trouble finding a way to get enough light on my plant, when I tried growing it indoors.
- Plectranthus x 'Mona Lavender' leaves are green on top and dark purple underneath. Easy to keep alive indoors, but best color requires ridiculous amounts of light. My main problem with them has been water-related: a potbound plant dries out too quickly, but when I repotted, the plant died. (suggested by Don and Kapt'n Splash in comments)
- Many but not all Saintpaulia (African violet) varieties will get red undersides to the leaves under good conditions. Saintpaulia and I have a troubled history, so I don't recommend them personally, but many, many people get along with them very nicely, and hey, you might be one of those people.
- Saxifraga stolonifera's (strawberry begonia) leaves are gray with a red back. It's usually a very easy plant; mine are being weird at the moment and I'm not sure why.
- Stromanthe sanguinea 'Magicstar' has dark green leaves with white flecks and a red-violet underside; 'Triostar's leaves are pink underneath and irregularly brushed with white and green on top. Both are approximately Calathea-level difficulty; I've been successful with mine, over reasonably long periods, but not everyone is so lucky.
- Syngonium erythrophyllum has dark green leaves with red undersides; I have only ever seen it for sale on the (now defunct) Asiatica Nursery and have no idea what it's like as a houseplant. (suggested by tay696 as Syngonium)
- Some cultivars of Tradescantia zebrina (green/silver on top, red-purple beneath) or Tradescantia fluminensis (dull olive green on top, purple beneath) qualify. It's also possible to turn a T. zebrina that's supposed to be purple green by not giving it enough light; I think in those cases the underside turns green too, but it's been a while since I've seen it so I'm not sure. T. zebrina is easy to grow, if prone to running a bit out of control; T. fluminensis didn't do well for me indoors the one time I tried it. (T. zebrina suggested by Tigerdawn)
- -->I'm open to other ideas, if anybody can think of other plants that fit the category.<--
1 "Bamboo ginger" is also the common name of Costus stenophyllus, which looks nothing like this and has leaves which are solid green on both sides. Just so you know.
2 Except maybe for Zingiber malaysianum, which did very nicely for me for a very long time, though we're having some relationship problems at the moment. Some of this is Sheba's fault.
3 (Which is technically Euphorbia umbellata now, but sometimes I have trouble letting go of the names.)