hmm...couple of issues...
The pedals you have now weren't designed for clips, you can kludge a solution and make it work but those are just kind of the wrong tool for the job. I would run powergrips with them if anything.
MKS sylvan touring pedals are great, they're like the steel rat traps that came on every 70s/80s road bike ever, only high quality. But I wouldn't reccomend them for someone new to clips, as they don't have any little tab or anything to help you kick in. I run them and can get in ok most of the time, but in shoes without much tread it can really be a pain. If you don't have super-wide feet the road or even the track versions will probably do you better, as will some of those performance pedals somebody linked. If you do get the touring version, you might want to put a little bolt in one or both of the other set of reflector/clip mount holes to give yourself something with a little traction. There is some aftermarket thing that somebody on here showed me, too, but bolts seem to work fine.
Sheldon thinks strapless toeclips are way jingus, I've never run them but I can't see how they'd do much for you, but then again I only run clips and straps on a fixed gear so my needs are different.