What's the "best" way to decide a size for spritesheets for best performance?

I have a general question about spritesheets. I like to stick to square power of 2 sized images, like 256x256, 512x512, etc. However what if I wanted to make a spritesheet having 3 sprites along the x direction and 3 sprites along the y-direction (total 3x3 = 9 sprites)?

Would I start with a square power of 2 image, and divide it by 3 along the x and y directions? I kinda didn't want to do this because if I'm using a 256x256 spritesheet, 256/3 is like 85.33333 - so 3 sprites won't fit in evenly with the pixel-nature of the image. One sprite might have to be 86 in width with the other two being 85. Should I care about that?

Or the other way I was thinking was.. should I think about each individual sprite's size first? As in starting with "Alright, I want each sprite to be 128x128" and then calculate the spritesheet's size off that? The thing with that though that I was thinking is it won't necessarily stay a power of 2. If I wanted 3x3 sprites still, the spritesheet would end up being 384x384, and I wasn't sure if that was bad too.

Or maybe do I have to stick with a "nice" number of sprites along each direction? (like start with a nice 256x256 spritesheet, but have to use maybe like 2x2 sprites (which fits nicely cause they'll each be exactly 128x128) or 4x4 sprites (making each 64x64)?