I have an iBook 800, RAM maxed out. Keynote is excellent considering it's a 1.0 release.
With some themes, typing and rotating graphics is a bit slow, apparently it makes use of AltiVec (I asked some guys working on Cubes and they said that it is ok). When playing videos in presentation modes the framerate drops to about 10-15 fps (don't have numbers though, it's just my educated guess). Strangely, video playback nearly without any dropped frames in editing mode.
But still, Keynote is really worth it ... I wish it would have arrived one day earlier, because I've had a presentation the day it arrived (found it in my mailbox after I came home).