Crap, I just lost my post
And it was brilliant I tell you, brilliant.
OK short version: Optimal would be AFP to OSX, NFS to linux and Samba to windows, but that's a ton of work to do something rather simple.
Why not AFP+NFS+SAMBA?
You have a life, and better things to do.
Why not NFS?
Most linuxcies default to serving NFSv3, since it's robust and easy to setup. OSX defaults to only wanting NFSv4, and you can't (or at least two OSX sysadmins, myself and another linux sysadmin couldn't in two hours) get it to mount NFSv1/2/3 via the GUI. You can do it through the command line with enough flags, but they don't make it easy. Besides, I haven't heard a single good report about mounting NFS from windows.
Samba is easy as hell to setup.
Samba is really chatty, but not so much that it will flood your network. It's also nowhere near as optimized as NFS (IMO & tests), but it's not so slow you'll notice it under most conditions.