If you want to go SPD (where the cleats are recessed from the sole so you can walk in the shoes, as opposed to SPD-SL where the cleats aren't recessed making walking much less comfortable), then commonly recommended pedals are Shimano PD-M520 which have clips on both sides of the pedal, or Shimano M324 which have clips on one side, platform the other.
Apparently Lidl start their bike-stuff sale tomorrow, so if you want a cheap pair of SPD-compatible shoes then you might try that, otherwise I think shoe choice is a really personal thing so try to find somewhere to try them on.