とりあえず今気にしているのはCPUそのものの速度ではなく、
digitalWrite()の速度
です。
で、いろいろググったら知りたかったことが書いてあるブログにたどり着きました。
http://blog.livedoor.jp/prittyparakeet/archives/1061895937.html
やっぱりdigitalWrite()はMEGAの方が遅いということのようです。