In reply to Tyler: Hard to know what the line is between hilly walk and decent ridge or something. But short of the going to the Highlands, I think your best bet is to go to Galloway. Fairly accessible but still very quiet and remote-feeling.
It's all pretty rough going in that area, some good bothies. I've stayed at White Laggan twice, I like it a lot.