Cleon
Legend
They're tough but do lousy damage, so methinks CR2 would be plenty.
As for Advancement, a Giant Bombardier Beetle goes Large at 5 HD, and a Giant Stag Beetle starts out Large at 7 HD. I think I prefer the Stag as the size-step, so how about:
Advancement: 5-6 HD (Medium), 7-12 HD (Large)