Right, so that's our first criterion: cost limited to trade-in price of the 6s. Actually I don't know what that is, but if it rules out the S7 it probably rules out other recent flagships (because being recent there won't be many second-hand examples around).
The HTC 10 is the only one of those that I'm somewhat familiar with, and the only one with expandable storage, but it is a recent flagship. There's an offer on if you buy it direct from HTC, but that still leaves the price at £470 - I don't know what the resale price of an iPhone 6s is, but I'd have guessed less than that. I like it myself: my wife has one and it's solidly built, responsive, and like the Samsung's it has capacitative buttons rather than on-screen (leaving more screen space for you). The user interface differs a bit from a Samsung, but Samsung software is different from any other Android so you'll get that with any other brand.
The 6P has been out for almost a year, but as a Nexus you can still expect a long software support lifetime. People who own them do seem to like them. Only the 32GB silver version is still in stock at the Play Store (the next Google phone is due very soon, so stock of both the 5X and 6P is being run down), no idea what the second-hand prices are like. As storage is not expandable you should make sure you buy one with enough space for your needs. The 5X would be a cheaper option, but the largest capacity 5X only has 32GB (too little for me these days, your requirements may differ). If you can afford it and like large phones the 6P would be better.
The One+ 3 will be cheaper, but I don't know much about it.
If you like Samsung and are not worried about expandable storage then last year's S6 and Note 5 would also be options to consider. Or even the Note 4 (which has replaceable battery and expandable storage, but is of course older).
Sony's seem to be popular in the UK at the moment, and the previous generation (Z5) would give expandable storage as well as waterproofing. I've no personal experience of them.