I think Open SUSE would be a good next try, it's very GUI driven, so the installation process would be similar to Ubuntu. Note that apt-get will not work in SUSE, but it has it's own package management and repository system.

I'm giving up on Xubuntu, it seems to not be the answer.

Gentoo is more for relatively experienced users, and same with Arch. By advanced, I mean there's more manual work in the terminal.