There are no absolutes in life, so I'll amend pls8xx's statement: The new wall will very likely fail if constructed as you say. You're in a freeze-thaw part of the country, which is why your footer needs to be below frost line. If you attempt to "float" the footer, the expansion and contraction of the soil will heave and crack the footer, the mortar joints in the CMUs, and the brick veneer. You also need to consider that with a 3' high wall, the forces attempting to knock it over are pretty intense. Without being tied to a proper footer, and without vertical steel reinforcement, those forces will eventually win and your wall will very likely fail. Again, no absolutes in life; the brick piers on my 100 year-old house go 6" into the ground and sit on bare earth. But if you're taking the time and expense to do something, why build in the probability of failure? As to the EP Henry wall solution... did that quote also include demo & removal of the existing wall and related sitework? If so, they may not be that out of line. If you approach it as a DIY job, you may be surprised at how quickly $X per ton of disposal adds up. If you do the project yourself, be fanatical about following the manufacturer's instructions. These systems are designed so they can be installed without special masonry skills, but you still need to be very accurate in preparing the base. If you don't feel like you're spending a ridiculous amount of time getting the first course of block perfectly level... well, you're probably not doing it right. If you want to put a fence back on top of the wall, Keystone makes a system that'll hold the fenceposts securely within the structure of the wall. Might be worth looking at. Best of luck!

Look at multi-flow drainage systems on google. You need drainage. It probably should have had a wider footing going back toward the slope (called a cantilever wall - the backfill sits on the footing like a fat guy on a chair so that the back of the char can't tip over). He built what is called a "gravity wall" which relies on the mass of the wall being greater than the force of what is being retained so that it won't move. Any water build up behind that wall causes what is known as hydrostatic pressure which adds to the force being applied to that wall. Weep holes would have been a good idea during construction. Now it is a bit more difficult to make the weep holes. At minimum, put in drain pipe and clear drainage stone behind the wall so that the water can get out. What was built is a typical basement wall built to support something on top of it and with a structure holding the top of the walls apart and a concrete slab holding the bottom of the walls apart. He is essentially asking a vertical slab to hold back 40" of fill without pushing out or toppling over.

Let me start by telling you that you have a beautiful garden! I brought in the expert to look at your question and offer an opinion, the hubby is a bricklayer and has plenty of experience with retaining walls. You, unfortunately, have way too much soil that needs to be held back to prevent the wash out that will occur without a full retaining wall. The terraces would erode rather quickly if you just had retaining blocks stacked loosely. Their strength is in having them stacked tightly with the gravel interlocking them. Sorry to disappoint. Good Luck, Tracy & Ed

You have been given so many really great suggestions that I don't think I could think of any that are better or more helpful. I did however want to address the "ugly" wall. It is possible to colorize your wall with what is generally known as "white washing" but by adding a cement additive you can tint it any color you would like. It's very simple really. You would need a bag of white portland cement, a bag of white hydrated lime and the colorant powder of your choice. Mix the portland and lime 3 to 1 and add water so it's a milk consistency then add the colorant until you get the color you like. Measure the colorant as you add it so subsequent batches will be mixed to the same color depth. Brush it on with a paint brush. The painting goes faster than you would think by sort of swishing the brush in all directions to fill all the little crevices, You have about 30 minutes or so to work the cement mixture but if it starts to stiffen just add more water and mix well again and finish up. I did this on my very old cement stucco house this past summer and it is the brightest shiny white you could ever imagine. It looks beautiful with freshly painted trim. Anyway this will work on anything with cement like texture (bricks too) and because of the added portland cement it will not wash away like a simple lime only solution will eventually do. You could even do a really bright color like red or deep blue if you wanted to and consider it an art wall if you wanted. Just something to consider in addition to plants. Any left over materials can be mixed with sand added to make stepping stones or cement planting containers etc. Good luck!