Extremely interesting thread, informative too, I refer back to it every now and then.
Well, it seems as if enough information has been given regarding CPU requirements. However I think XaoS is a good place to start for beginners to fractal geometry. It does not do 3D, but it has a wide variety of preset formulas for exploration as well as an option to use your own formulas. I always felt that it helped me to warm up to this type of math and to grasp the fundamentals. After this it is much easier to use Mandelbulb 3D (or at least it was for me).
Also, if/when you begin using Mandelbulb 3D you may want to look for a cheap external hardrive. I just recently got one to clear the 35 Gigabyte parameter folder from my desktop (and I'm sure people around the forum have much larger folders than that).
I think in my recent past I was getting a bit ahead of myself on the big learning curve. XaoS might have been a good starting place to jump in. But I find Fractal Explorer meets my own basic needs nicely. It does do 3D, but that is a side of Fractal Explorer that I've had trouble with. Chaoscope does 3D, but you have to keep the shapes simple or else the result can look messy.
I've had probs with Mandelbulb 3D partly because...well, it isn't as simple to use as the aforementioned. I just don't know much about formulas, I barely know an X-axis from a Y-axis, etc. I was getting a basic grasp of the rudiments, however (thanks to Lenord!) but as I mentioned elsewhere, real life took me away from the art world for a good while, and by the time I found some leisure, my smattering of knowledge of MB 3D had faded away... Currently I'm just focusing on learning how to get good looking high quality 2D fractal images, before I dive recklessly back into the realm of 3D once more... The other trouble has been the extreme slowness of rendering on my small system (and for that matter, lack of hard drive space for saving).