TL;DR: Tefillah is called avodah sheb'lev because it's the only service that can be done in the heart, as opposed to an actual action. Furthermore, it's reminiscent of the original form of avodah, that of offering karbanos in the Beis HaMikdash.
The quote you are referring to is:
לאהבה את ה' אלהיכם ולעבדו בכל לבבכם (דברים יא:יג). איזו היא עבודה שהיא בלב? הוי אומר זו תפלה
"To love Hashem and to serve him with all your heart" (Devarim 11:13). What service is done with the heart? You must say this is Tefillah.
Note that the Tur (OC 98:1) had a different wording of our Gemara:
וכתיב ולעבדו בכל לבבכם. וכי יש עבודה בלב? אלא איזו היא עבודה שהיא בלב? הוי אומר זו תפלה
And it is written, "To serve Him with all your heart." Now, is there a service in the heart? Rather, what service is in the heart? It must be this is prayer.
According to the Tur, it seems, the Gemara is asking what service is in the heart, as service implies doing something, not just thinking about it. Thus, the passuk must be referring to prayer, which is the only thing you can actually do without performing an action. (Speech isn't called an action - Makkos 4b.)
He thus explicitly disagrees with your statement in the question that
when I think of service of the heart for example I think of all my whole being acting, according to what HaShem told according to His Torah; not only because He told so, but because my inner most being wants to serve Him out of the love, respect etc. I have for Him. For me it's the outward actions that show the inner part that I would like to call service of the heart.
It's the opposite, in fact. It's what's inside that counts; your actions might be a "service," but they're not "of the heart."
While we're on the topic, I'd like to point out the second Mishnah in Pirkei Avos:
שמעון הצדיק היה משירי כנסת הגדולה. הוא היה אומר, על שלשה דברים העולם עומד: על התורה ועל העבודה ועל גמילות חסדים
Shimon HaTzadik was among the remnants of the Men of the Great Assembly. He used to say, on three things does the world stand: on Torah, on service, and on kindness (emphasis mine).
What is the service mentioned in this Mishnah? The Bartenura says it's Karbanos, and the Tosfos Yom Tov agrees. But Rabbeinu Yonah expands on this concept, noting our Gemara in Taanis, and says that prayer is what is referred to here. Furthermore, now that we don't have the Beis HaMikdash, the tefillos are in place of the Karbanos. He brings several other proofs that the tefillos nowadays are equivalent to the karbanos in the times of the Beis HaMikdash.
For one more parallel between the physical avodah of the Karbanos and the mental avodah of tefillah, here's a quote from the Midrash (Vayikra Rabbah 7:2):
מי שהוא עושה תשובה כאילו עלה לירושלים ובנה את בית המקדש ובנה את המזבח ומקריב עליו כל הקרבנות שבתורה
One who does Teshuvah is as if he went up to Yerushalayim, built the Beis HaMikdash, built the Mizbeiach, and brought on it all the Karbanos in the Torah.
So we see that one who davens with a full heart isn't just equal to bringing karbanos - after all, you can only get credit for whichever karbanos you bring under a specific circumstance, and it's impossible for every karban to be brought at once. But when you daven, you get credit for bringing every karban in the Torah!