Helium328PU:
According to 32u4 datasheet (here, page 208), there could be up to 7,8 % error rate. Thats quite a lot. But there is not a field for 16 MHz XTAL.
I don't know what exactly you are referring to. My 32u4 datasheet has a table 18-12 which shows Baud rates for 16MHz and there is no error at 250k, 500k or 1000k.
HOWEVER ... the Arduino Leonardo and Micro communicate with the PC over the USB cable at the full USB data rate and the selected baud rate is ignored. (I think you must, nevertheless select a baud rate with Serial.begin() ). Consequently I think that if you are using a 16MHz Arduino then one that uses a 32u4 would be best for your project. However I have no experience of the faster and more expensive DUE and its brethren.
I don't know anything about HID USB - I thought that was just for when you want to pretend that the Arduino is a keyboard or a mouse.
I don't use my Leonard or Micro very often. However my standard baud rate with 16MHz and 8MHz Atmega 328s and Attiny 1634s is 500,000 - and I have never noticed a problem.
...R