Is there pallet/package optimization program that would look at the unit of measure table to compute the number of packages or pallets to determine the best method of packing thus maximize density and space.
Looking for something that would do Rate Shopping at the time of Sales Line entries
I have never heard about a fully integrated add-on for NAV which does pallet/container optimization. But there are many external solutions which can help you with this, not that I have tried to work with any of them.
As for you other question, then it depends of what kind of rates you are looking for. Lanham's eShip add-on comes with shipping rate integration, if that's the right kind of rates.