Actually, I've stored luggage at PGH's counter with no problems, and no charge whatsoever. They struck me as particularly nice there.
I'd tend to favor the Southside idea - when you arrive at Pittsburgh, head straight out the doors and to your left - you should arrive at an intersection between a busway dumping out to the street, and another street (Grant I think), cross the busway, and proceed straight two blocks or so, where you will see the Light Rail Subway stop called Steel Plaza, catch this two stops South to Station Square, where you'll find a number of restaurants as well as the Monongahela Incline, which you can ride to the top to the Mount Washington area for a dinner with a view. Returning to the station, you just reverse the process.
