С точки зрения "максимального количества достопримечательностей" я бы в южную половину Молдовы и Буджакскую степь не ехал, а сосредоточился на северной и центральной Молдове. Можно еще прихватить кусочек Винницкой или Хмельницкой области вблизи Днестра. Но здесь, как я понимаю, ключевым словом является "чтобы понравился жене". А в Молдове ландшафт действительно непростой, не уверен, что он понравится человеку, отправляющемуся в свой первый поход.
С точки зрения достопримечательностей предлагаю обратить еще внимание на Западную Украину в районе Тернопольской и Хмельницкой областей. Ландшафт там тоже не сахар, особенно вблизи Днестра, но есть возможность какого-то маневра.

Что касается косы Лебедевка - Приморское - дороги там нет. Рыхлый песок, бОльшую часть пути придется идти пешком. При достаточно широких покрышках кое-где удастся ехать по мокрому песку вдоль линии прибоя. Кроме того по весне рыбаки могут прорыть канал в косе для захода рыбы в лиман. Его преодоление даже летом не всегда приятно, а в мае это совсем проблематично.