Put shelves up high over your toolboxes. Make them on both long sides so you maximize storage, with the side opposite the boxes up high enough you do not bump your head. Use the cheap L-shaped brackets that are formed out of sheetmetal, strong and no diagonal piece. Mounted to the studs of course. Not sure on overall height, you might get by with two shelves over the boxes and one on opposite side. Maybe a U-shape top shelf all the way around, and then extra lower shelf right above the boxes?
You could rip a 4x8 sheet of 3/4 plywood into 16-inch widths, and get all of your shelves out of one sheet.