I have to say that I find almost all of Edinburgh charming. Of course, you don't want to stay in Ian Rankin location, but you won't find and B&B's there so no worries. New town was new in the late 1700's so bear that in mind. :) I've stayed off Dalkeith Road--beautiful views of the Salisbury crags. I've stayed near Calton Hill and enjoyed it's easy access to Princes street and the Royal Mile. I've stayed closer the Royal Botanic Gardens and enjoyed being out of the tourist area, but still and easy trip to Prince's Street or The Royal Mile. We did stay way out to the West of the castle time, and that was probably my least favorite location. But that was so long ago that my memory is unsure.
You don't need a car in Edinburgh. I always start at the Castle no matter how many times I go to Edinburgh. It's the views, it's the history. It settles me into the city. I love the Georgian House in New Town. It think it gives a marvelous view of life at the turn of that century! Gladstones Land will give you a view of medieval Edinburgh. The Museum of Scotland is wonderful. You start in ancient history at the bottom and climb to the 21st century on the top floor. Whisky Center was a bit funky and lovely intro to whisky. Check to see what exhibits are at the National Art Museum. I've seen some lovely ones. All the art museums are great. One thing to do is to walk to Stockbridge along Leith Water Walk and end up at the modern art museum. I do like the Place at Holyrood as well. If you're politically inclined tour the new Scottish parliament.
As for nature, climb Arthur's Seat if you have the proper weather. My favorite castle with a bit of a garden that you can reach be train is Stirling. It has marvelous history as well. If you just want to walk in hills a bit, you can take the train to Birnam / Dunkeld. There are some lovely walks and you can see the sweet little town that also has lots of history.
As for pubs there are so many. I like Sandy Bells for the music.