As a native (American) English speaker, I see no problems with your question (or the the other answers). I'd say the the "Excuse me" softens the question sufficiently to use it with a person you don't know.
However, if you wish to soften the question further, you can use the subjunctive. Adding a degree of "hypothetical" makes it even less of a demand.
Excuse me, where would I find the eggs?
Pardon me, where would the eggs be?
Another approach for softening requests is to ask about the request, rather than request directly. (This is seen in using "Pardon me, but do you know the time?", rather than the more direct "What time is it?")
Excuse me, do you know where the eggs are?
Alternatively, you can simply state your situation, and rely on the listener following social conventions and answering the implied question.
Pardon me, I'm looking for the eggs.