It's good that you asked the question. A complete answer will take several steps (many of which others have given, but are important enough to repeat).
There is something fundamentally wrong-headed about describing the statement that the primes are the building blocks of the integers as "philosophically unsound". To be philosophically unsound, something must be philosophical. But Tao's soundbite is a standard shorthand for a mathematical fact.
You say the basic argument is
An integer can either be expressed as a product of smaller integers or not. If not, it's called "prime".
Then you point out that this itself is not a very exciting fact or very special to the primes: one can make similar statements for the powering operation and for lots of other things. Your second observation is absolutely correct. But what you called the "basic argument" is not at all the statement in question. It is not in fact an argument at all: it is just the definition of a prime number (among integers greater than $1$). The statement that the "building blocks" refers to is much more profound and comes in two parts:
Part I: Every integer greater than $1$ can be expressed as a product of prime numbers: that is, for all $n > 1$, there are prime numbers $p_1,\ldots,p_k$ such that $n = p_1 \cdots p_k$. (Note that we allow "products" in which $k = 1$: these are precisely the prime numbers. This point sometimes confuses beginners.)
Part II: The factorization into primes is unique in the following sense: if
we write
$n = p_1 \cdots p_k = q_1 \cdots q_l$
where $p_1 \leq p_2 \leq \ldots \leq p_k$ are primes (taken in increasing order) and $q_1 \leq \ldots \leq q_l$ are primes (also taken in increasing order) then $k = l$ (i.e., the number of factors, or blocks, is the same) and $p_1 = q_1$, $p_2 = q_2$, all the way up to $p_k = q_k$.
Taken together, Parts I and II are called the Fundamental Theorem of Arithmetic, and this is the argument in question.
As an aside, let me note that with the usual goodwill we extend to the infinite set of natural numbers, Part I is almost obvious: you take $n > 1$. If it's not prime, then by definition you can write it as $n = ab$
with $a,b < n$. If $a$ and $b$ are not prime, you repeat. After every step the largest factor gets smaller, so certainly this process terminates eventually: that's Part I.
Part II is highly nonobvious: it was first (essentially) proved by Euclid, and in a university-level course in which students had not seen this material before I would probably spend two full lectures on the proof. The fact that it seems like it should be obvious is a piece of psychology that one has to get past in one's study of this subject. (Why? Because in fact there are many other natural contexts in which one wants closely analogous results to be true and they're not! In the mid 19th century, the French mathematician Gabriel Lamé thought he had proven Fermat's Last Theorem because of a mistake like this!!)
Do you see why Parts I and II together can be well paraphrased by saying that the primes are the building blocks for the integers (again, let's say integers greater than $1$)? Think of each prime as being a kind of block: picture maybe an actual block which has the number written on each face. We have an infinite supply of each kind of block -- imagine a bin receding out into the distance with "2 blocks", another one with "3 blocks" and -- well, there are a lot of blocks and bins. Then to "build" just means to take finitely many blocks altogether from the bins: you can take more than one block from any given bin. Then you take the blocks and multiply them together to get a number. Every number can be built that way: Part I. More profoundly, if you show me your final number then -- given enough time! -- I can deduce exactly what your blocks are. For this imagine that you have built something incredibly complicated out of a bunch of legos that are all the same color. From far away it's not clear at all what legos you used. But once I start removing legos -- factoring! -- then eventually I will of course end up with exactly the same number of legos of any given shape and size as you did. (Perhaps this analogy is bad in the sense that it makes Part II look obvious. But I think it helps in understanding the statement, so I won't mess with it.)
- It would be more precise to say that the primes are the multiplicative building blocks of the integers: the building operation is multiplication, and after all there is another operation in play as you perceptively point out. In this sense, their role is absolutely special: they are the single blocks. If you want to change the operation then the statement certainly does not apply.
So let's change the operation...to addition. Now we had better include $1$, because that's our building block. In fact, in contrast to the multiplicative situation in which there are (thanks to Euclid again) infinitely many building blocks, in the additive situation there's just one block, the number $1$, and of course we get any positive integer $n$ by adding $1$ to itself $n$ times. This is true and important...but obviously much less interesting than the multiplicative situation (I got a flashback to the joke 1980's videogame "Quayletris"), so you can perhaps forgive mathematicians for omitting the word "multiplicative". In fact there is a mathematical sense in which the multiplicative structure is obtained from "infinitely many copies" of the additive structure. This is presented formally in problem G1
from the first problem set of my number theory course. Note though that the G stands for "graduate level": if you do not have some training with abstract mathematics, I am afraid it might not make much sense.
Finally, what makes the integers interesting is precisely the fact that we have both additive and multiplicative building blocks. Taking each separately on its own terms we have a completely transparent structure. But when we start mixing the two, we get tough questions alarmingly quickly. Take a prime number $p > 2$. Is $p -1$ prime? No, it's even. Okay, is $\frac{p-1}{2}$ prime? Not necessarily, but in plenty of examples. Infinitely many times? Yikes: we don't know. Okay, take $p> 3$. Is $p-2$ prime? Not necessarily, but in plenty of examples. Infinitely many times? Yikes: we don't know. Well, in the latter case we know tremendously more now than we did two years ago, but that's another story.
Added: I read the end of your question more carefully, and you do indeed seem to be asking about the privileged role of multiplication in number theory. I think that actually is a more philosophical question, because when you actually study mathematics (as I see from your profile that you have), you find that multiplication is incredibly important and ubiquitous. One of the most important abstract structures in all of mathematics is the ring, which is a set endowed with both additive and multiplicative structure (and at least a few reasonable axioms relating them). The ring of integers has been incredibly interesting and important for at least two thousand years. Are there mathematical structures which abstract the powering operation, for instance? Yes: off the top of my head I can think of restricted Lie algebras and divided power structures. But at most 1% of all mathematicians seriously care about either of those, whereas everyone needs rings. One way to say it is that whenever you have an additive structure, then the collection of maps from that structure to itself which preserve addition is a ring, the endomorphism ring of the structure. (Look up additive categories to see this in detail.)
I would go so far as to say that studying this kind of generalization of multiplication too seriously is a bit of a trap. Moving from addition to multiplication and exponentiation and beyond as operations is a nice intellectual exploration that probably every mathematician makes at some point early on. Armed with the thrill of discovery, it is natural to wonder whether these higher operations -- tetration and beyond -- might actually be more interesting, especially since you don't hear much about them in school. Well, they could have been -- I don't know of a convincing "philosophical" argument that explains otherwise -- but they're not. It becomes a bit of a black hole, and in fact most people who are highly engrossed with tetration turn out to be, if not a bit crankish, then certainly aiming away from where the real mathematical content lies.
In particular, you ask about the properties of integers $n$ which cannot be decomposed as $a^a$, $a^{a^a}$, and so forth. Well, I am a practicing number theorist and I'll give you a piece of practical advice: study the actual primes instead. They are much more interesting than your "primes under the powering operation". I can't prove it to you, but I feel very confident about it. In fact, to the idea that no one has thought of this before: I would say that a lot of people have probably thought about it for a little while and unfortunately some people have probably thought about it for longer than they should, when they could have better used their time thinking about something else.
Further Added: It might helpful to say a little more about why "powering-primes" are so inauspicious. The fascinating thing about the primes is that from a purely multiplicative perspective they are determined by Euclid's theorem that there are infinitely many of them, but when you interact them with the additive structure you get an amazingly rich and fruitful question: where are the prime numbers with respect to the natural (additive) ordering of the natural numbers? The two (incredibly old and famous) questions I asked above are special cases of that. In general, there is an entire branch of mathematics which is concerned with how the primes are distributed: this part of mathematics is deep, contentful and useful (i.e., has many, many applications to other parts of mathematics).
I am not clear on what the precise definition of powering-prime being proposed is, but certainly numbers which are not powering primes should lie among the perfect powers, i.e., numbers $a^b$ for $a,b > 1$. Now the set of perfect powers is certainly well-studied in number theory. (For instance, it is a 2006 result of Bugeaud, Mignotte and Siksek that the Fibonacci numbers are perfect powers are precisely $8$ and $144$. This got published in the leading mathematical journal: it's serious!) Note that the perfect powers, although obviously infinite, form a very small set -- density zero -- in the natural numbers. So in contrast to the primes, which are infinite in number but rare, most natural numbers are (by any definition) powering-primes. Asking about gaps between perfect powers is also natural: the Catalan Conjecture, now Mihailescu's Theorem, is an important result there. So if powering-primes means "not perfect powers" then, sure, this is already a thing...but a thing which is subsidiary to the thing about prime numbers. (See Steve Jessop's answer.)
I should say though that from the OP's example I got the impression that by a powering prime he meant something that is not of the form $a^a$ (or maybe not of this form or $a^{a^a}$ or...: that comes to much the same). That is much less interesting: it's just the image of the positive integers under a rather simple increasing function, so it's quite clear "where these numbers are".
Best Answer
This is more like a comment but it's too long, so I'm putting it as an answer instead, please accept my apology.
In base $10$, the "symbol" $78152_{10}$ represents the number
$78152_{10}=7\cdot 10^4 + 8\cdot 10^3 + 1\cdot 10^2 + 5\cdot 10^1 + 2\cdot 10^0$.
In base $n$, the "symbol" $78152_n$ represents the number
$78152_n=7\cdot n^4 + 8\cdot n^3 + 1\cdot n^2 + 5\cdot n^1 + 2\cdot n^0$.
You can see that we prefer to call a base by the number that is raised to the power of its position from the last digit. That is why we call it the base.