I would say it depends a lot on the scene and the hardware.
BI:
Some tests rendering the default cube scene at 960x540 pixels:
Tile size: 32x32
Render time: 00:01.02
Tile size: 64x64
Render time: 00:00.89
Tile size: 128x128
Render time: 00:00.86
Tile size: 256x256
Render time: 00:00.87
Tile size: 512x512
Render time: 00:01.27
A more complex scene at the same resolution seems to go faster with larger tile sizes:
Tile size: 32x32
Render time: 01:53.57
Tile size: 64x64
Render time: 01:46.15
Tile size: 128x128
Render time: 01:45.26
Tile size: 256x256
Render time: 01:43.22
Tile size: 512x512
Render time: 01:43.09
Using the same scene at 960x540, I roughly timed the amount of time it took to render one tile. (This estimate is very rough because the time changes dramatically between different tiles, I just timed one tile):
Tile size: 120x67
Render time: 02:23.89
(approx. 12
seconds per tile)
Tile size: 64x64
Render time: 02:33.31
(approx. 6
seconds per tile)
Tile size: 300x300
Render time: 02:24.60
(approx. 30
seconds per tile)
Tile size: 200x200
Render time: 01:49.57
(approx. 10
seconds per tile)
Tile size: 100x100
Render time: 01:42.43
(approx. 14
seconds per tile) (fastest)
The fastest time here has the same settings as the slowest setup for cycles:
At 500x500:
Tile size: 128x128
Render time: 00:41.53
(fastest)
Tile size: 100x100
Render time: 00:41.92
At 512x512:
Tile size: 100x100
Render time: 00:43.67
Tile size: 128x128
Render time: 00:47.84
Cycles:
Using Mike Pan's famous BMW benchmark scene at 960x540 with 10 samples:
Tile size: 64x64
Render time: 01:51.03
Tile size: 100x100
Render time: 02:02.03
Tile size: 128x128
Render time: 01:49.64
Tile size: 200x200
Render time: 02:00.39
Some tests to see how much varying sizes and using powers of two affect render time:
At 500x500 px:
Tile size: 100x100
Render time: 00:46.86
Tile size: 128x128
Render time: 00:53.42
At 512x512 px:
Tile size: 128x128
Render time: 00:50.54
Tile size: 100x100
Render time: 00:49.46
Conclusions:
To find a general rule for deciding optimal tile sizes for any kind of scene, one needs a lot more testing data with long renders etc.
To really look at this in detail, I think some addon which would send tile settings and render times to a database would be necessary.
IMO, Setting the tile size to ~100x100 or ~200x200 and adjusting to fit evenly in the render dimensions is good enough.
However, from the tests I did above it does seem that maintaining a consistent tile size helps.
Power of two tile sizes seem to have no apparent effect.