Why would you apologize for looking for a theater? It should be "excuse me," not "sorry."
I'm sorry to disturb you, but I'm looking for the theatre is what you'd use in Norway at least.
Извините, мы ищем ядерных судов! (Nuclear vessels!)
You're welcome, you will never forget what that verb means now. ;-)
I'd probabvly use "..ищем атомные суда" or "... ищем ядерные суда". Genitive is really outdated here (and confusing because суд means "court of law" and has the same Genitive plural as «судно»).
Because it implies an imperfective aspect, meaning that it doesn't specify when, where, or how often. For example, "whenever we travel to a new city, we look for the theater."
If we're asking for directions right now, at this specific moment, then it implies a perfective aspect. For example, "we're looking for the theater [right now]."
"we look for" is the incorrect aspect. It sounds as if you do this in a continuous basis, not a specific time. For example, "we look for the theater every time we go to a new city, and today, we are looking for the theater in Moscow."
It looks OK to me (native speaker of English). Where are you from?
It's hard for exercises to be totally lifelike, because they are constrained by what has been learned by this point. But I can see this as part of a conversation: "Sorry, we're looking for the theatre. Which is the correct building?" Why do you say it is "SO wrong"?