I, too have been searching for a midi sequencer that is more affordable than logic express, and more powerful than garageband. (being able to use a laptop for midi will be essential when I purchase a Mac to replace my P166)
I've used two on the PC - one by Voyetra (it can print notation), and one by cakewalk (I prefer it for sequencing (recording)). I haven't checked Voyetra for Mac software, Cakewalk's (Mac) offerings seem slim also.
From what I know - one has to make sure the software is not only for the correct OS, but also platform (Intel or PPC).
That out of the way, here is what I've found:
Easy Beat - about $50, but I believe it won't work on intel.
Intuem 4 - about $80 - and I think it supports intel.
Better on the prices! But, when I purchased cakewalk for the PC - it was no more than $30, and included the midi cables (to game port). (I purchased it at a local Best Buy)
PS - on a side note - you could run paralells (or fusion - it's free) - and then run windows software (like voyetra or cakewalk) .... but that's a 'clumsy' way to do it.
And there is the question - will the software communicate with the interfaces - and without lag... (I'm not too concerned about lag - since my p166 laptop can handle my midi recording (Roland XP-30 and Yamaha DX-27) just fine. It can also play back without any problems.
Voyetra has a sequencer for $20...