Some solid suggestions for a budget. I'd second the point about Legos being too expensive for regular brick-building, though. Even if you buy the basic brick sets in bulk, it's still not cost-effective.
A better way to build brick walls is with the same material used for so many other terrain pieces: pink insulation foam. You can get a huge plank of it at Home Depot for about $12, and that will last you a very, very long time. Just use a sharp hobby knife and a straightedge to cut it into bricks, and build a wall with PVA glue. Make sure you prime it by hand, though, as the propellants in most spray paints will melt foam.