I can't say enough good things about the Elmview (www.elmview.co.uk) - hands down the best B&B I have ever stayed at, for the very reasonable price of £95. Huge, gorgeous rooms and the best breakfasts we had in the U.K. (They offer the traditional Scottish breakfast but always have something different as well, which is awfully nice after two weeks of "full English breakfast"!) They have a small private car park a short distance away, which is nice if you are driving. Lots of wonderful restaurants within a few minutes' walk, and the castle and Royal Mile are about 10-15 minutes' walk.

And only 5 minutes' walk from Arden Street...