bitfloor did it correctly
limit orders should get a fee RETURNED
market orders should pay the fee
Or at least passive limit orders (ie. won't execute immediately) are free.
On top of that, order fees should be flat + % (eg.
BTC0.01 per trade, plus 0.5%). That will kill the micro-trading bots.
On top of that, there should be a fee for cancelling short-lived orders. Say, any order that lived in the book less than 1 minute gets charged
BTC0.01 cancellation fee. You get five free cancels per 24 hours (plenty for fat finger fix-ups), plus for each execution you get a free cancel (so people can actually do trading if they want). Or something similar that would stop quote-stuffing.
Sounds good in practice, but the logic behind the system might be hard to keep track of.
Taking what you've stated in the OP and what btc-e.com does, I think it would be a good idea to charge a small trade fee 0.1% or less and charge a withdrawal fee as well.
Understandably, brokers have to make a profit from somewhere too.
I would also charge a licencing fee for anybody who wants to use the API as developers using these API's are the ones that place the most strain on the system. Thinking out aloud, free for basic use would be a good idea but then $10 or so a month for trade placing will put off kids running 1 cent scalping bots.