" it was tricky in Gmail to import a complicated set of folders like I have and retain the structure"

I did it through a client (mail.app), synching with IMAP. It worked flawlessly.