Fullcount, you'd be foolish to replace your platform/clipless combo pedals with cage-and-strap (dangerous and inconvenient) or strapless half-cages (more trouble than they're worth). You have the best setup right now. Use 'em on the platform side with some good firm-soled walking shoes or skate shoes, and keep an eye out for a deal on SPD mountain-bike shoes. I found Pearl Izumi X-Alps in a clearance bin for $28, and they are great: efficient and comfortable on the bike, walkable and comfy off the bike, and quite hard-wearing.
Another alternative would be pinned BMX platforms with stiff skate shoes, but I would stick with what you have.