I'm not sure if "easing" is really that noticeable in LEDs vs simple linear, but give it a try and tell us what you find!
But definitely you'll want to remember that the eye's view of brightness is logarithmic against actual energy and compensate for that. Otherwise the rate of change of a LED going from dark to bright will seem to slow down as it gets brighter.
Actual threading is going to be a bit hard on an Arduino, I did not think that a thread library existed... but you never know its a big world! Send me a link if you have actually used threading!
I would use an object that tracks each intensity and destination intensity. And include a "next" call to update to the next intensity (for speed use Bresenham's line drawing alg, not typical high school algebra). Then loop over each object calling "next". Hook this loop into the timer if you want it to happen in the background.
There is code that does a lot of this here http://code.google.com/p/arduino-m5451-current-driver/source/browse/trunk/latest/apps/suntree_nightlight/suntree_nightlight.pde. Look at the RgbFader class. You'll have to adapt to shift-brite though.
www.toastedcircuits.com: Lightuino LED driver