Erm.. ok, I know you meant well but you seem to misunderstand it a bit. You CAN search the market's entire repository (whether it's a CLI or a GUI hardly matters when it comes to the basic operation). It can also, clearly, install.

The difference between the Android Market and a package manager is that Android Market isn't DOING very much more than downloading an "apk" file and placing it into a specific install location and then tracking that that download had been made no that device. The apk isn't unzipped, processed or anything. The apk is loaded and run the same way any zipped up "jar" file in Java is loaded and run. A Debian package manager has to download, decompress, examine and process a package in addition to placing the decompressed files into their appropriate locations relative to the root. Processing the package includes running any dependency checks, pre-deploy scripts, post-deploy scripts and so on.

There's clearly far more to a package manager than downloading and dropping a file. The advantage of the Android Market is that it generally "just works" in a sandbox riddled virtual machine environment like Android. The advantage of Debian package management is that it can work "outside the box" and perform operations ANYWHERE in the OS as root and even intelligently process OS config files and do ANY useful things that a package needs to do. The disadvantage to the Market is that it can only really do things to applications--never really touching the OS in other paths in the system (although there are tricks to get around that, mind you--but it's still difficult, generally). The disadvantage to Debian is that it requires a strict discipline to be followed and makes it more complicated and would make it less secure if a repository snuck in.