Sevastopol sucks. Personnel is unfriendly like in old Soviet time when they think they do you a favor letting stay at their hotel. Breakfast included in price room is shitty and the same each day. You can choose either eggs or sausages but not together. The only good thing is that the room was really big, actually there were 2 rooms and a room for baggage and a lot of closets. Oh and an air conditioner which came in handy when it was 30+C outside. And I lived in their best building. So I suggest not to stay there.

I usually don't stay at hotels in Moscow, I prefer staying with friends so I don't know a lot about hotels but I can suggest Izmaylovo Hotel, Building "Delta". The room cost from like $120 (standard).

The official site http://www.izmailovo.ru/eng/rooms.php looks kinda out of date but there's a lot of other booking sites/companies. The hotel is located not in the center of Moscow but not too far. You can get there by subway (Партизанская/Partizanskaya station, blue line) it's like 20 minutes from the city center and a 5-10 minute walk from the subway station to the hotel.

A couple booking companies I found on the net which have English version:
http://www.moscow-hotel.ru/eng/izmailovo.php
http://traveleng.sitenow.ru/izmail/

For about $12 you can have a great breakfast. You come in a huge hall full of all kind of dishes and you can choose any amount of any dishes and eat it for hours till you can't stand from the table :)