MCC003 (Verbatim 8x DVD+R), MCC02RG20 (Verbatim 8x DVD-R), Yuden000-t02-00 (Fuji 8x DVD+R 50 pk, Best Buy), TYG02 (Fuji 8x DVD-R 50pk, Best Buy)
Well, if the burner is working fine and burning properly, good media should give you very good to excellent quality burns. Also, rdgrimes gave you some very good information. I'll add to it:
yuden000-t02-00 on a px-716a (Plextor) is great burned at 8x or 12x, but awful at 16x with fw's 1.07 and 1.08
MCC003 (8x rated) usually does very well burned at 8x or 12x
MCC02RG20 (8x DVD-R) burns well at 8x for some, and a few also can burn it at 12x with great results--but depending on the burner.
The reason I was told one should not burn media below it's rated speed (i.e., 8x at 4x) is because the dye is expecting and formulated for an 8x burn. Sometimes the burner and the dye on the media will allow 'overspeeding' with still a great burn--like 8x media burned at 12x--but that's not true with all 8x media.
The best way to discover what media burns best at what speeds (e.g., 8x, 12x) is to do the burn quality testing and compare a burn at 8x and 12x with the same media (of course, see if that 8x media can be overburned with that burner). If both are just as good or very close to the same results, then that says you can burn just as well at the faster speed. However, if you do a burn at 8x that's great with said media, and one at 12x and it's noticably worse, that tells you it's likely the best idea to only burn that media at its rated speed of 8x.