The biggest difference between them, IMO, is that Unreal comes from an AAA lineage and has relatively recently started extending its reach down to mobile and indies, while Unity comes from a mobile (iOS) / indie lineage, and has been steadily extending its reach towards greater and greater AAA ambitions.
What this means for users is that they're really both converging towards similar capabilities, but they come at it from different beginnings. Both companies have a huge staff dedicated to ongoing engine development, very capable people all around, so you shouldn't make the mistake of assuming that Unreal is somehow more legitimate. In practice, Unreal has put a lot of effort into user-friendlier tooling with UE4 but there are still more and sharper rough edges than in Unity's tooling. Unity is more friendly for the casual developer, but sometimes the fact that they assume lesser of the average Unity user can get in the way -- Usually you can get around it, but it sometimes seems like more work than it ought to be, or that what you need is more hidden.
Licensing is also a big difference -- both in terms of access to the C++ source code (which you might come to need for performance tuning) and in cost to you to license either engine for commercial use. Unreal offers up C++ source code access for free, while Unity charges ~$50,000 last I checked. For usage, Epic wants 5% of your gross revenue above $3000 per product, per year, but there's no seat license -- this is nice and simple; its also entirely free if you're using it to make CG films, IIRC. Unity wants $75/month subscription or $1500/one-time fee per seat, per platform-package (e.g. extra iOS, Android features, Consoles -- which I think are a higher fee), but they don't take a cut of your sales after that. Depending on what platforms you target, how many developer seats you're licensing, and how many sales you expect to do, one of these options will save you money; If you make a lot of sales, Unity works out to be less expensive in the end -- the break-even point is lower or higher as a function of how many seats and platforms you license, and whether you need C++ source; but, you pay unity up front, regardless of whether you make any sales at all. Unreal costs more when you're successful, but it doesn't penalize you if you have a commercial failure -- 5% is really never a burden. When I worked it out once, basically if you make less than a couple hundred thousand in sales, Unity is the cheaper option; if you make more than that Unreal costs you, but making "too much money" is a wonderful problem to have and you'll probably be overjoyed to give them their 5%. That 5% is definitely cheaper than a team of high-caliber engine developers.
That said, whichever is most comfortable and has learning resources and a community that suites you is probably the way to go. Your game is always more important than the engine, and these engines and toolsets are already close enough to parity that either will block you from achieving your vision.
The Liscense has a reference in it that you can contact them for custom liscensing, But I don't know at what point that would be viable.
But I agree, having to pay Unity/Epic is a good problem to have :)