re: "But what if we find they worship the same God humans do? "
After I posted that, I figured someone would point this out.
Most major religions in the world believe in one God, creator of the universe. Perhaps we are all worshiping the same god, but just in our own way.
What would really be interesting if a alien race had their own version of Jesus (God come down to their planet in their form).