So, I know that the fees of a “normal” exchange would probably be best, however on occasion I may want to use one of them because of the speed/simplicity (and because they are both built into the Coinomi mobile wallet).
I haven't used Changelly since I heard a few horror stories and Shapeshift had everything I needed. I don't think the fees are that bad. They tend to reflect the taker fee on exchanges (which is worth it for the convenience and lack of KYC). Maybe there was a slight markup beyond that, but I had multiple order books open last time and the fees were reasonable.
According to changelly.com they charge a 0.5% fee and shapeshift.io charges only the miner fee. However, A) are there any hidden fees that I should be aware of (like several transaction fees or an inaccurate exchange rate), and B) have you ever run into any trouble using them?
People complain about the outgoing transaction fees on Shapeshift (mainly when exchanging to BTC), but it's just like withdrawing from an exchange. Granted, some exchanges (like Poloniex) and brokers have better withdrawal fees for BTC.
Fees have been very high (0.003-0.006 BTC) to withdraw from Bitmex lately, for comparison. I've used Shapeshift five or six times, no complaints. I feel better using them than Poloniex or Bittrex, where I'm constantly worried about getting my account locked.