Packaging is a very big achievement. Even Android use packaging with APK file. Really, packaging is not the problem. I remember systems before packaging, this was a nightmare. Never return to this hell...
The problem is to have popular tools able to build and publish proper *.deb package as easy as for *.apk packages. For example a good IDE where you find a "new C++ Debian package" button (and others language option of course), fill a simple form and start coding your application from a functional template. Then a "build" button should create the *.deb package and you should be able to debug it. The IDE should have a "Add Debian repository" button with a simple form to create a remote Debian repository using FTP or SSH. Finally the IDE should be able to publish your packages in your remote repository. Like for Android, the IDE should be able to build package compatible with a choice of releases.
From my point of view, the packaging is not the problem. The lack of competitive developers tools advancement in the Linux distribution compared to Android is in my opinion far more the root cause if the problem. While structured very differently, *.deb and *.apk packages target almost the same goals from the system and user point of view.
The situation in creating and publishing *.deb package is actually like if you create and publish *.apk packages all by hand using a lot of command line, instead of a easy and shiny IDE.