Fedora Budgie or Atomic Budgie or even Ubuntu. Basically since these gets them back on familiar territory with Budgie and should give them a good experience with all bases.
Too early in my Solus journey so not comfortable to personally recommend it yet.