감사합니다 is based on chinese and 고믑습니다 is a purely Korean word. So sar as I know, either is equally acceptable. The verb ending determines the formality.
I put in "Excuse me. Thank you" and it said Another correct solution: "Excuse me. Thank you" which was exactly the same thing lmao
Should it be 실례합니다 감사합니다? Since it's impolite to use 고맙습니다 to a stranger? or if it's someone you know but not quite friends with yet?
It's not impolite to say 고맙습니다 to strangers. You usually say 실례합니다 if you need to get by someone in your way (or 잠시만요), or if you want to ask a question to a stranger.