The eggbeaters have gotten very good reviews amongst recumbent riders with 4-sided entry (no need to get it aligned properly) and self cleaning (not that mud is going to be a major issue on roads). A very simple mechanism compared to a lot of the other pedal systems I've seen - KISS applies...
Here's a photo from the Crank Brothers website.
They come with cleats included.
I have noticed the right pedal seems to engage & disengage a little easier than the left, so hopefully its just a matter of working them in