I know we should all be brainstorming and working on a new fee market.
But fact is, it will still take some time and in the meantime users will
continue to shout insults at us for the high "fixed" fee of 0,1 mBtc.
Even banks sometimes have less fees. (1 of 5 Play Store reviews of
Mycelium seem to mention high fees recently)

My suggestion: until the market is established let's lower the minimum
relay fee per kb to something less. 0,01 mBtc comes to mind. (of course
pulling this number out of thin air)