Ok, so here's what is working better right now. First I worked on the USPS config, and the final is:
Click image for larger version.  Name: usps.jpg  Views: 48  Size: 42.4 KB  ID: 12837

Then, I worked on the shipping config (which I really KNOW-NOTHING about, so I just guessed), here's what I ended with:
Click image for larger version.  Name: shipping-conf.jpg  Views: 65  Size: 15.4 KB  ID: 12838

First to answer your question on how I will ship 1/messenger bag and 2/sandals? I will have to use 1 medium for the handbag and sometimes 2 boxes of sandals may fit into a Lg F/R box but not always, so I will have to use 2 Md. The store owner doesn't have a problem of loosing 2-3 bucks in the shipping but 2 x 20 is $40 so I will try to be as much accurate as I can. Anyway they usually offer many discount coupons and specials which are really good deal to shoppers.

Now back to this issue. With these settings if someone buys 2 sandals and one messenger bag, it will be 3Md boxes $37.05. If they order 1/1 it will calculate 1Lg box $16.85.

Now the problem is that if someone orders 3 perfumes (18#) it should calculate Md box, and is going to the large one.

So maybe if I understand better the Shipping/Packaging settings and the percentage:weight formula, I will pin this down.