From Kitzur Shulchan Aruch 18:12
לאחר השמונה-עשרה אומרים אלהי נצר וכו׳. וקודם עושה שלום וכו׳ כורע ופוסע כך שלש פסיעות, כעבד הנפטר מרבו. הפסיעות יהיו בינוניות, ולכל הפחות כדי שיתן אגודל בצד עקב. ולא יפסע פסיעות גסות ולא יפסע יותר מג׳ פסיעות. פוסע תחלה ברגל שמאל ואחר־כך ברגל ימין, ושוב פוסע ברגל שמאל
Quick translation:
After Shemoneh Esrei say "Elokai Netzor etc.", and before "Oseh Shalom etc." bow and take three steps, like a servant departing from his master. The steps should be of middling length, and at least enough to place his toe to his heel. And don't take huge steps, or more than three. Step first with the left foot, then with the right, and then again with the left.
From Shulchan Aruch HaRav 123:5:
וכשפוסע עוקר רגל שמאל תחלה לפי שדרך הליכת אדם בסתם היא לעקור רגל ימין תחלה לכן עוקר כאן רגל שמאל תחלה להראות כאלו כבד עליו ליפטר מלפני המקום ומטעם זה אטר רגל עוקר תחלה שמאלו שהוא ימין כל אדם
Quick (and loose) translation:
When one steps, they should move their left foot first, since the way a person normally steps is with the right foot first, therefore, here we move our left first to show that it is difficult for us to leave G-d's presence. For this reason, a lefty should step with his right foot, since his left is everyone's right.
(This could be taken to mean that at the beginning of Shemoneh Esrei, you start with your right. Tzarich Iyun.)