I have two recommendations for you:
1. Avoid transfers at CAI. International and domestic flights go from different terminals and there is no (intelligent) way to connect between the two. I ended up taking a taxi, which actually leaves the airport and then comes back in. The domestic terminal is not very nce. Things may have changed in the last three years, but I doubt it.
2. Try Condor from DUS. I flew to Hurgahda once (another airport that is a bit of a bit) on my way to Soma Bay and my one charter experience was actually pretty decent.