Well, here's what comes to mind.
- Bowing is not reserved for G-d. There are many cases in the Bible when prominent Jews bowed to kings such as the prophet Natan bowing to David (Melachim 1:1:23) and Yosef’s brothers bowing to Yosef (Breishit 42:6). Even Avraham (Breishit 18:2) bowed to strangers whom he suspected of being idolaters (Rashi to verse 4).
Bowing in the direction of the Ark (or Aron Kodesh, as I shall call it) is not bowing to the Aron Kodesh at all, but rather bowing in the direction of the Holy of Holies in Yerushalayim (Jerusalem). When there is no Aron Kodesh (like a minyan that is not in a synagogue), we bow in the direction of Yerushalayim. Wikipedia (quoting Rambam and Shulchan Aruch) says:
"...the Aron Kodesh should be placed "in the direction in which people pray in that city," i.e. toward Yerushalayim. The Shulkhan Arukh records the same rule, but it also recommends that one turn toward the southeast instead of east to avoid the semblance of worshiping the sun".
The law is (not sure if this is across the board) that if the Aron Kodesh is not on the eastern wall (for whatever reason), one faces Yerushalayim irregardless, and does not face the Aron Kodesh.
The Shulchan Aruch Harav says:
"...One should turn towards Eretz Yisrael if they are in the diaspora, and to Yerushalayim if one is in Eretz Yisrael, and towards the Temple if one is in Yerushalayim. We are located in the west so we face east, and therefore we put the Aron Kodesh on the eastern wall, however, even if the Aron Kodesh is on a different wall, one should still face east"
As regards why we should pray in a specific direction at all if G-d is everywhere, I seem to remember learning that the main thing is that your heart be pointed (focused on) towards the Holy of Holies because that is where G-d's presence was strongest on earth.
Edit: (Thanks to Tom Shmuel for the source)
The Mishna (Berachot 4:5) says that if one is unable to face Yerushalayim:
"he should direct his heart toward Yerushalayim."
As regards what you were taught in hebrew school, my guess is it was probably over-simplified - depending on how old you were. When I was young, I was taught similarly, but the truth is one is forbidden to worship idols in any way. Some idols are worshiped, not by bowing, but by other means, i.e. throwing rocks at them (source here), sacrificing one's children (not Isaac style, they went all the way, (according to some1)), sacrificing animals to them, burning incense, as well as other things we won't mention here. The point is, worshiping an idol in any way that we worship Hashem is forbidden, as well as worshiping them in any way in which they (specifically) are worshiped. But it must be an idol, or the intent must be that it is, for it to be forbidden. Bowing out of respect to someone is not worship.
1: Some do say that they just passed them through fire.