Safety of random nonce with AES-GCM?
Is this an issue?


That's up to you, not us.  Is 2^-33 probability of horrible cryptographic failure acceptable to you?  Multiply that by the number of times you'll use this construction (or the rate and the product life time) to get a scarier picture but one you should keep in mind.


  Is there something else I should prefer?


"should prefer" is again subjective based on your situation.  I strongly advise you to consider AES-SIV (or AES-GCM-SIV) or XSalsa20-Poly1305.


  For example, AES/CBC with encrypt-then-MAC construction would have a more reasonable IV/nonce size of 128 bits.


Sure, for another example.  But if collisions bother you and you'd like a significantly lower probability then either 1. stop using random nonces 2. go for a nonce size that's greater than ~80*2 (a la XSalsa) or 3. Use a misuse resistant algorithm.