For another option, I'd suggest you first nip into the nearest library, and borrow their copy of the Lonely Planet "Walking In Scotland", which is an excellent source of inspiration and basic information.
Armed with that, if you want hills rather than mountains, then the Scottish Borders are your best bet. Walking In Scotland has a whole chapter on this area. I'm a big fan of the area around Hawick (especially some of the villages about), which is surrounded by the Teviot Hills, but it is a bit of a faff to get to by public transport... There's no train nearby, so you're going to have to get a bus.
That said, there are fairly regular buses from Hawick into Edinburgh, as the X95 from Carlisle to Edinburgh runs through there. If you'd rather one of the villages nearby, that's when things start to get really tricky. Some friends used to live in Denholm, which had a lovely pub and great walks nearby, but we always had to get there by car.
Hawick itself seems a pleasant enough town (I've not spent much time there), with several options for places to stay. A quick google reveals a number of walking routes from there, either along the valley or up into the hills. If you don't want mountains, you should find plenty of nice hills around here.
Otherwise, look through the Walking In Scotland section for the Scottish borders, and look for descriptions of other places and walks near hear that inspire you!