I don't have any recommendations, but consider this: RPM works on 3 distributions (SuSE, RedHat/Fedora, Mandriva). DEB works on 2 (Debian, Ubuntu/Kubuntu). Fringe distros use even different formats.
But RPMs of different distros often need to be slightly different.

You could look at how other companies do it. Most of them, I think, just write custom install scripts.