IMHO, depending on the geometry of the recumbent, flat pedals (or more precisely, a lack of foot retention) is somewhere between a mild annoyance and a recipe for a broken ankle. I'd generally advise against it except during the early stages of learning to ride a two-wheeler.
But if you insist, I'd suggest a nice big set of BMX/MTB platforms with plenty of grippy bits. Gravity's against you, so having as big an area to try to keep hold of as possible is what's likely to help. I'll defer to the flat pedal users for suggestions of what that might be.
(If you're allergic to clipless, might PowerGrips be an option? They're slightly more awkward to get into than SPDs, but an order of magnitude easier than toestraps, and work with any kind of shoes.)