Best data structure for a queue with random reads?
Take any dictionary data structure and link its entries in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure.

In search trees, this is called threading. It gives you constant-time access to the first and last element, respectively, and maintaining the threading takes only constant-time overhead for each dictionary or queue operation. As a consequence, you get $\Theta(\log n)$ access by key, $O(1)$ access to front and back of the queue (without modification), and $\Theta(\log n)$ insertion and deletion.

If you use hashtables you get $O(1)$/$\Theta(n)$ (AC/WC) access by key, $O(1)$ access to front and back of the queue (without modification), and $O(1)$/$\Theta(n)$ (AC/WC) insertion and deletion. The usual caveats apply.