If the East-West route finally happens, it's a no-brainer to extend a segregated bike lane eastwards along Waterlloo Place, Regent Road and Montrose Terrace as far as London Road. Only 'tricky' bit is which side of Waterloo Place to use: maybe both? One way each side... Then double lane on southern side of Regent Road, replacing extremely under-used car parking. Then on south side of Montrose Terrace, which is the quitter side, hardly any shops, not much parking demand.
Ideally you then carry on along London Road, through Meadowbank, and on to Portobello Road. However Lothian Buses might have something to say about that...
London Road west of Easter Road junction is crying out for a segregated bike lane too. North side makes the most sense, as only one junction between Easter Road and Elm Row. Could connect to segregated lanes at new Elm Row junction which will eventually replace that horrendous roundabout.
These two cycle lanes would eventually create segregated routes linking York Place and Princes Street with routes to the east of Edinburgh, Portobello, etc.