Best Tile Size for Blender Internal Renderer and Cycles
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.