I've stayed at four hotels in Sofia on business and the one I'd stay at if visiting with my wife would be the Grand Hotel Sofia. Rooms are quite large and modern, very comfortable beds.

Nice park in behind the hotel, pleasant outdoor patio/dining area, centrally located, close to the national theatre, art galleries, shopping on Vitosha and good restaurants.