they have an ENORMOUS FEE
Just like all other Bitcoin wallets that I'm aware of, Mycelium is free. It's not
their fee.
Most wallets allow you to choose your own fees, but due to the low supply of space in blocks (1MB per block) and high demand for space, the fees that you will have to pay if you expect to get confirmations on your transaction within a normal timeframe are going to be pretty high.
There's not a lot you can do about it, but one minor thing that you can do is choose a SegWit-compatible wallet and move your coins to a SegWit address.