Why are distant galaxies not actually tiny bits of matter? Distant galaxies are said to be moving away from the Milky Way (and us) at speeds approaching the speed of light. Since Special Relativity tells us that any object moving away from us at a velocity of near the speed of light will increase in mass in our observations, i.e. it will appear to be much more massive than its rest mass, approaching infinity as the speed approaches the speed of light. If we observe very large masses (like galaxies) moving away from us at near light speed, wouldn't their rest masses be tiny? So why do we not think these distant galaxies are actually just specks of matter in terms of their actual rest masses? And if that is the case then are we not just looking at what may be sub-atomic particles moving away from us at near light speed? ...The expanding universe explanation is the standard one. The balloon example is perhaps suggestive but not correct. If you occupied one point on the surface of a balloon, and you had a friend next to you and the balloon expanded, your friend would move away from you at a relative velocity v. Einstein's equations would obviously still apply. I see no easy way to explain why when I look at measurements of relative velocity between distant recessive galaxies, those velocities are somehow not what are measured and quoted but something very different because the universe is expanding. Velocity is defined (for Einstein too) as distance divided by the time to travel that distance. And we are talking about objects with mass; not a reflective beam from a searchlight or something like that. Even if the universe expands, velocity is still what it is. And if it is not what it is, then why do astrophysicists state that distant galaxies are moving away from us at nearly light speed? I guess I would like to see the intuitive argument with equations included which must be there but no one knows how to do it. I suppose it took a while before time dilation could be explained on the back of an envelope too.
 A: Let us not forget that in addition to far-away galaxies at high redshift we can observe nearby galaxies (and many at every distance in between). Those observations of nearby galaxies can resolve individual stars which are clearly the same as stars in our own galaxy and obey physics consistent with the physics that powers our very own Sun.
Further, the mass of galaxies is measured by observing their velocity curves (indeed this was the source of the first part of the missing mass puzzle).
In short, no: there is no chance that we have made an error of orders of magnitude on the mass of these objects.
A: It is not true that Special Relativity tells us that "any object moving away from us at a velocity of near the speed of light will increase in mass in our observations". This statement depends on what observation you make, ie if you measure the relativistic mass or the rest mass. For cosmological observations the relativistic mass is not usually an interesting quantity. There are various ways to estimate the mass of galaxies, one is for example gravitational lensing, which has the merit that it also takes into account dark matter. Or you can look at the angular velocities of stars orbiting the center which depend on the total mass (also takes into account dark matter). Either way, what you get is the total gravitational mass (energy) in the rest frame of the galaxy, ie its rest mass.
A: If your argument was right, we would be so confused when handling accelerated electrons in laboratories, confusing them for galaxies.
Even based on my very limited experience with relativity, the very basic formulas for energy and momentum account for this. Hence, there is a difference between rest mass ($m$), and observed mass ($\gamma m$). So rest assured, if these formulas were correct, galaxies should be huge.
A: What special relativity tells us is that a body moving with a velocity $v$ which has a rest mass $m_0$ will have an observed mass of $$m = \gamma m_0$$ where $$\gamma = \frac{1}{\sqrt{1 - \frac{v^2}{c^2}}}$$
This still holds true in astrophysical situations. For example, the apparent brightness of objects called quasars is much larger than it's "real" brightness due to a very similar effect.
But what is actually happening is that space itself is expanding. No doubt you know that the farther an object is from us, the faster it is moving away from us. But the velocity with which it is moving away from us isn't due to the velocity possessed by the object itself but rather the velocity due to the expansion of space. 
Think of two dots on a balloon. If you blow into the balloon, the two dots will move away from each other at some speed. But this isn't because the dots themselves have a velocity, it's because the space in which they are in (the balloon) is itself expanding. The situation with the universe isn't exactly analogous, but it's somewhat similar. 
Therefore since the bodies themselves don't possess a relativistic velocity, what we actually measure is the rest mass of the object.

P.S - Lots of astrophysical papers do talk about this quantity called "peculiar velocity", which is infact the velocity possessed by the object itself. This peculiar velocity is the velocity over and above the velocity of the object due to the expansion of space. How the difference between the two velocities etc., are measured and calculated are beyond your question (and this answer), so I'm not going to get into it here, but I thought it was worth mentioning that astrophysical object do have their own velocities (on the order of a $100$ to $1000$ $km$/$s$).
EDIT: Special relativity applies only to inertial frames of reference with respect to us. The expansion of space is an accelerating and hence a non-inertial frame of reference. So one will have to use general relativity equations (which I'm not too comfortable with).
However it is useful to to remember that the increase in mass of a relativistic object comes from the mass-energy equivalence. The total energy of a body with momentum $p$ is given by $$E = \sqrt{p^2c^2 + m^2 c^4}$$
Consider you and a friend standing at two points in space. If the space is expanding with some speed, you and your friend will be moving away from each other, and therefore light from him will be redshifted with respect to you. But he isn't gaining energy by moving away from you, both of you are just standing there. Therefore the mass that you measure will be the same as his rest mass, since $p = 0$ in the above equation, and $\gamma = 1$.
A: The usual answer (as noted above) comes from an empirically consistent standard cosmology for which space itself expands.  Evidence includes
1. the cosmic microwave background with its origin near the early recombination epoch, redshifted by the expansion to the current temperature of 2.7 K
2. the baryonic nature of luminous matter as indicated by spectral data
3. the agreement of WMAP, BAO, supernovae and many other tests for distance measures to high redshift
If you were correct we would have difficulty explaining the details of astrophysical phenomena observed at the lower redshifts, such as star formation regions and active galactic nuclei. Don't forget that observations begin with our own solar system and Milky Way, which appears not that different to other spiral galaxies. 
Having said that there is a sense in which you are correct, because a high redshift galaxy could well be another form of a molecule at rest in the laboratory, since matter potentially contains all other matter by the laws of QFT. Even the standard cosmology (which is well open to debate these days) would agree that there are string theory dualities between very distinct scales and there is no reason that we should not apply these ideas to our view of the cosmos. 
A: I thought that since I brought this up and I didn't get any good explanations, I'd answer it myself. Plugging in some numbers helps. I used this for light speed = 299,792.458 km/sec. Hubble constant = 72 km/sec/megaparsec. The Hubble constant is necessarily an approximation because nobody knows exactly what it is and they also don't know if it is a constant through time. The Hubble constant is used to calculate the speed of distant galaxies due to the expansion of the universe. So based on some simple calculations using the above numbers, I come up with this: If you go out 13,573,936,292 light years, the universe is expanding at 0.99999999994 of the speed of light. I might point out that this is about 203 feet per hour slower than the speed of light so it is pretty close. Using the Lorentz Transform (relativity) we can figure out the effect on a galactic mass moving at that speed away from us. Suppose we observe a galaxy about the size of the Milky way or Andromeda moving away from us at this speed. The rest mass of the Milky way or Andromeda is roughly 700 billion solar masses. Give or take. Applying the Lorentz transform to this observation, the rest mass of the distant receding galaxy would be about 7,493,550 solar masses. So even at speeds this close to the speed of light, this is still a large mass. It is not a tiny particle as I thought it might be. Therefore we don't even have to use the hand waving argument about the expansion of the universe doesn't really count in relativistic calculations. I guess the real theoretical issue and question would be: what happens at the singularity? That is right at the outer edge of the expansion, objects are traveling exactly at the speed of light, and here relativity breaks down. But nobody knows the answer to that. The interesting thing about plugging in the numbers is that when you are really close to light speed, there are no contradictions. And my calculations are really close because 203 feet per hour is a lot slower than I walk. I could crawl faster than that.
