We went to Marseille over New Year and loved it. It does have a reputation, overwhelmingly undeserved, but some might find it a little rough and ready in places.
Of course I would say this, but Denmark actually hits everything you want, except a) it's a very long way round if you don't want to fly/ferry b) not exactly cheap.