Right now, Palm is in the middle of desiging their App Catalog for the Palm Pre smartphone and future webOS devices. We can see some of their ideas from the current "beta" version, but I really hope they make different choices from Apple here in the final product.
First, Apple's store has two main categories for apps: free and paid. The free area is mostly a bunch of "adware" and "lite" versions of more fully featured programs. There are some free interfaces to other services there too, like the Kindle and eReader apps that let dowload books you've bought through other web stores. There's a role for free apps on the Palm App Catalog, and I feel this should be a category.
However, I think paid should be divided up a bit. I'd look at Amazon's MP3 store as an inspiration. They have a bargain area (the $4.99 and down page), but they they also break out albums by different price points and have top seller lists for each one. By creating more lists with natural exclusions, they give the ability for more albums to have "top spot" and get exposure. On their "hot lists", they don't even list price.
I'd love to see Palm have a "99-Cent Store" section, perhaps with a bit of a downmarket skinning to it. Set up a social expectation that 99 cents is the price for toy applications, but premium/serious apps are found in a separate part of the store. Perhaps we wouldn't see as much of a race to the bottom then. Especially with the smaller market that the Pre will have in its first year compared with Apple's juggernaut, it's important to make sure that the developers can make some money on the device to get a healthy ecosystem going.