I myself was ruined when my first Gaited horse was a $70 grade paso at the local sale barn. She is smooth as glass, but like many is only 14.1-14.2. So like you I wenl looking for a bigger horse, Most everyone I know who has gaited stock rides TWH or some variation, and within those ranks they go from beautifully smooth running walk on down to a jarring pace. I fell into the world of rocky mountain horses and found my personal prefrence here, now that is not to say that there are no "bad" ones in the RMH world, but they fit our needs.
I would say with a little bit of research yo can find almost anybreed in a 16hh variation, as there are alot of people here stateside who are looking for a bigger horse. But if I knew that I needed a 16 or 16+ gaited horse I would likely concentrate my efforts to looking at TWH, only because there are more of them around.
Now that said, You may want to sit a couple examples of the different breeds, because sometimes with size the feel and movement of the gaits will change.
If I may, why are you so dead set on a 16hh horse? Just personal prefrence? Do you think you are to big for a smaller framed horse?
I find a lot of people who mistake height for stoutness in the world of field trials, so see alot of people struggling with 16.2 horses when a slightly thicker 15hh would have done the job.