Lesson learned from changing harddisk in my Debian GNU/Linux etch using udev-Mac Mini: Remember to create /dev/console on the new disk. Otherwise the kernel will just stop dead and say that it could not create an initial console.
After that was fixed (running mknod manually from an install cd), something complained about /dev/null (although the boot completed), so maybe it's worth remembering creating that node as well.
It took some prying with four knives to open the Mac Mini, but from there - provided slim enough screwdrivers - it wasn't too bad.
This guide has nice pictures.
The Apple-supplied 4200 rpm harddisk could deliver around 25MB/s according to hdparm -t. I replaced it with a Hitachi 7200 rpm, and get around 44MB/s instead.
Update: One downside, though: the new harddisk apparantly runs hotter (which, I guess, would figure), meaning less time-to-noise when the machine gets (even slightly) loaded. Oh well.