I have the same size tank as you and am rocking the Yellow Tang Cleaner Shrimp combo and its really cool to have, and its a blood red cleaner shrimp so it adds some nice color. When looking for the tank you do want to find a relatively small one, preferably with no nibbling on the fins but you could probably get away with some really small marks if you QT, but thats just my opinion. You want to make sure there is no HLLE, which is something alot of tangs in pet stores have, mine had it but it was like 20 bucks and I could not pass it up. You want it to be really yellow, and most tangs should be really curious, so if its hanging out in the back of the tank alot its probably not your best choice. It should be interested in what you are doing and whats going on around it. I added my tang in the middle of the current addition process and then from there added a small clown fish and then a sang sifting goby and there really was not a problem with either addition, the goby and the tang fought over the top notch position for about 2 days and then there was peace. Do some research on the HLLE(Head and Lateral Line Erosion) so you know what you are looking for there, and also do some research on what you need to feed them, because from what I have seen, and am relatively new to this game, they have some strict feeding requirements compared to other fish. I know my tang gets more vitamins a day than I take in a month.
And about the iodine with the shrimp, i do a 5 gallon water change every week to week and a half and have never supplemented with anything, and about 2 days after every water change i see his old "skin" stuck to a power head when I wake up in the morning, I think he is dead everytime for some reason, still gets me after like 20 molts.
And after looking at your avatar I think you will be fine, he has the full 4 feet in the front to swim plus the sides so you should be good aslong as you dont get a big one to start.