There is a limit to how small you can focus an ideal single-mode laser beam. The product of the divergence half-angle $\Theta$ and the radius $w_0$ of the beam at its waist (narrowest point) is constant for any given beam. (This quantity is called the beam parameter product, and is related to the $M^2$ beam quality measure you may have heard of.) For an ideal Gaussian ("diffraction-limited") beam, it is:
$$\Theta w_0 = \lambda/\pi$$
So, to answer what I interpret as your main question:
Let's say that I have a laser beam of some given power that starts with some diameter $D_0$ at the point of emission and increases to $D_f$ at some distance $r$ away. Would this be sufficient information to imply a limit to the power per unit area (W/m^2) that could be obtained through focusing and what would that be?
The answer is no.
The parameters you have given are sufficient for calculating $\Theta$, but only if $r$ is large enough so that the points at which you measure the diameter are in each other's far field.
You would also need to know the beam radius at the waist, so you could calculate the beam parameter product. Then, to get the minimum spot size, you would need to refocus the beam so that it is maximally convergent. The absolute limit is the fictitious divergence half-angle of $\pi/2$, or 90 degrees, although in practice the theory breaks down for half-angles of more than 30 degrees (this number is from Wikipedia) since the paraxial approximation stops being valid. For an ideal beam at this impossible opening half-angle, this gives you a minimum waist radius of $2\lambda/\pi^2$. So yes, it does depend on the wavelength.
What lens characteristics and approaches would someone look for in order to do this with a laser pointer?
You need a lens with a very short focal length. This gives you the largest convergence. Note that the more convergent the beam, and the smaller the waist size, the smaller the Rayleigh range is. That is, the beam radius will get very small, but it won't stay very small, it'll get bigger very quickly as you move away from the focus. (The Rayleigh range is the distance over which the beam radius increases by $\sqrt{2}$.
In addition, thinking of a Gaussian beam as being "straight" is not quite correct. There is always a waist, always a Rayleigh range less than infinity, and always a nonzero divergence angle.
EDIT
Also, it is important to realize that there is no difference between an unfocused and a focused Gaussian beam. Refocusing a Gaussian beam with a lens just moves and resizes the waist.
The aperture size of the laser is not the same as the waist size. If the beam is more or less collimated, then the aperture will still be larger, because the waist radius is usually defined in terms of the radius at which the intensity drops to $1/e^2$ of its peak value. If the beam is cut off by an aperture at that radius, then even if it were close to diffraction-limited, it certainly wouldn't be anymore. So, apertures are always larger.
The waist is the thinnest point of the beam. Usually this point is inside the laser cavity, or outside the laser if there are focusing optics involved, which there often are. So still, the answer to your question is no. You are not missing the definition of $\lambda$; rather, you are comparing your minimum waist radius to the value of $2\lambda/\pi^2$ that I said was "impossible". I called it impossible, because to make a beam converging that strongly, you would need a lens with a focal length of zero!
Let's try a more realistic example with some numbers. Take your red laser pointer with $\lambda$ = 671 nm. Laser pointer beams are often crappy, but not so crappy as you might think, if they are single-mode. Let's assume that this particular laser pointer has an $M^2$ ("beam quality parameter", which is the beam parameter product divided by the ideal beam parameter product of $\lambda/\pi$) of 1.5. A quick Google search didn't give me typical $M^2$s of red laser pointers, but this doesn't seem to me to be too much off the mark.
Note that if you know the $M^2$ and measure the divergence of a beam, then you can calculate the waist radius. We are going to do that now. Suppose the laser pointer beam is nearly collimated: you measure a divergence of 0.3 milliradians, about 0.017 degrees. Then the waist size is
$$ w_0 = \frac{M^2 \lambda} {\pi\Theta} = \frac{1.5 \times 671 \times 10^{-9}} {\pi \times 3 \times 10^{-4}} \approx 1\,\text{mm}. $$
In this case, they probably designed the laser pointer with an aperture radius of 2 or 3 mm.
Now suppose you focus your collimated beam with a 1 cm focal length positive lens, which is quite a strong lens. The beam's new waist will be at the lens's focal length. That means you can calculate the divergence half-angle: it is the smaller acute angle of a right triangle with legs 1 mm and 10 mm. So,
$$\tan\Theta = 1/10,$$
or $\Theta\approx$ 6 degrees. Applying the formula once more to calculate the waist yields a waist radius of 3.2 microns, which is quite small indeed.
A "safe" laser pointer might have a power of 1 mW. The peak intensity is equal to $2P/\pi w_0^2$, so before the lens the peak intensity is about 600 W/m^2. After the lens it is about 100000 times larger.
So, to summarize:
- yes, there is a fundamental limit to the intensity, and it does depend on the wavelength, but you cannot even come close with a real-world cheap laser pointer.
- you need to know two of any of these quantities: divergence half-angle, waist radius, Rayleigh range, beam parameter product.
- really, the minimum size and maximum intensity depend quite heavily on what optics you use and how good they are.
Best Answer
What the others have already told you is that the pattern forming is a speckle pattern: each bump in the surface acts as a source for a spherical wave, these waves then interfere to produce this pattern. (The black dots and circles in the image below.)
In the wikipedia-article there is also mentioned the concept of "objective speckle pattern": when the reflected laserlight falls on another (smooth) surface after being shined on a rough surface, then the pattern on the smooth surface is, as wikipedia puts it, "the same regardless of how it is imaged, just as if it were a painted pattern".
Now you can imagine that your eyes are in the plane of a imaginary smooth surface where the light reflected from the rough wall is hit on. On this "wall" the pattern (the green dots) stays the same. When you move your eyes parallel to this plane, a part of the pattern disappears on the one end while a new one appears on the other end.