Blame the packaging tools, not the packaging format. AFAIK a .deb is a plain archive with packed files to untar in /, a description file, and scripts to run after and before installing the packaging. It cannot get much simpler than that.
In fact, the ipkg format used by the Palm Pre is basically a .deb file.

I personally didn't find the debian packaging tools that hard, specially considering a few months ago I did not even know where to start. As long as you don't distance yourself too much from what dh_make generates, of course.