If you do go for clipless spd-sl type pedals, then give Time RXS or Xpresso a try but NOT iClic which are made of cheese & dripping.
All Time pedals are regarded as having just about the best 'Float' known, the fore/aft & lateral movement between pedal & shoe, therefore foot.
Float is not just about the amount of movement allowed but also the feel/quality of movement & Time pedals have a 3 position 'feel' adjustment.
I dare say that Shimano pedals are of the highest quality also but can't vouch for the type of float they give.
Last but not least, when I 1st started out (not that long ago) the supplied pedals & toe straps supplied served me fine for a while with trainers.
As mileage & intensity of cycling increases though, pedals & cleats (I feel) offer much better support & comfort, barring other issues detailed in this thread.
Best of luck with it all.