Linux – have a Linux based Server which handles roaming profiles for Windows and Mac OS X

There are third-party profile management applications (like Flex Profiles). I suspect, however, that you're probably not redirecting the user's "My Documents" (and potentially "Desktop" and "Appliation Data") folders out of the profile, and this is probably causing a lot of data to fly across the wire that really should be "at rest".

I don't know how to tell you to configure Folder Redirection in a non-Active Directory environment other manual registry hacking, but this is very probably the "right solution" since it maintains the native Windows "roaming profiles" functionality but limits the amount of data subject to profile sync.

There's actually not one solution to this, but a kazillion.

The single sign-on that Active Directory does, is nothing more than Kerberos and delegation of credentials. We can do that too, using a Linux KDC or your old domain controllers. No problem: there's your domain users.

Roaming profiles exist (iirc, my Windows days are far behind me) in different forms: you can have the user data on a network share, or you can have (a part of) the user data on the local filesystem and some more data of the same user on a network share.

Both are possible, though the first is easier: with a something like NFS, or even GFS (which has some brilliant features for using it as a filesystem for shared home-directories), having home-directories - and thus user profiles - on the network is easy. Just make sure to use NFSv4 (or Kerberos enabled NFSv3, if you cannot pull off NFSv4) to provide some security and integrity of your data.

Having parts of the user data on a share and parts of it locally either means mounting, for example, /home/user/Documents over NFS again or using one filesystem to 'lay over' another one. I'm not sure how robust that is though, and I'd recommend you go for option 1: everything on a network share.

I'd also recommend hiring someone how know his Linux, btw. It's going to be tough to do this and be successful - both financially and technically - if you are doing this all for the first time. Good luck.