I know that when asking a favor from an adult that I am unfamiliar with, such as asking for directions, I should start with "Entschuldigen Sie..." but should I use the formal form when I am, for example, just trying to pass someone while walking?
Should I always say "Entschuldigen Sie" rather than simply "Entschuldigung" when dealing with people I don't know?
It depends. If you directly address a person, you'd use Entschuldigen (not: Entschuldigung) Sie. Yes, if you are not on familiar terms with them you'll usually use Sie, i.e. the polite form. (The usual exceptions, like students among each other, fellow sports(wo)men, adults addressing small children etc. apply, of course. The corresponding du-form would be "Entschuldige", interestingly without the "du".)
In this case it's easy to avoid the whole issue, though, by simply using "Entschuldigung" (or "Verzeihung"), i.e. the nominative. Matter of fact, if you don't want to strike up a conversation, i.e. you're simply passing someone by, stepped on their toes or whatnot, a simple "Entschuldigung" would be slightly more idiomatic, I think. "Entschuldige / Entschuldigen Sie" is really more like "Excuse me".
While they are generally mostly the same, "Entschuldigen Sie, [bitte]..." is orders of magnitude more polite than "Entschuldigung...". You will normally use the former if you want something from the other person, such as when asking for the way or asking for a small favor.
The single word "Entschuldigung" is not truly impolite, but it is much closer to yelling "Hey, you!" at someone. Which is however still appropriate, for example when you address someone who just left the café and left his wallet on the table without noticing.
"Entschuldigung" is sometimes even used, especially by elder ladies, as in "Entschuldigung!" (note the exclamation mark) while they accidentially-deliberately hit you with their elbow or run you over with their trolley in the supermarket because they felt you were in their way.
Yet another shade of grey a bit darker, we get to "Entschuldigen Sie mal..." or "Entschuldige mal [... du Depp]", which best translates to "Hey, what the hell...". It's something you would use if, for example, someone took your spot in the waiting line while you didn't pay attention for a second.
