Most small / cost effective way to detect changes in altitude?
TI's EZ430-Chronos is a hackable watch that uses their MSP430 MCU and lets you modify the firmware. It has an altimeter mode and uses the VTI Technologies SCP1000 pressure sensor.

I don't know anything specific about solving this problem or how accurate their implementation is, but VTI has an application note on using their part in an altimeter, and the EZ430-Chronos Development Tool User's Guide includes schematics for the watch, so you at least have access to a complete hardware and software implementation that you can evaluate and possibly carry over to your own design.

--- Edit:

When I posted my response I actually wasn't even thinking of just using an EZ430, but in terms of using it as a design reference since the schematics and source are published. But I guess it might make sense to just use one and tweak the firmware. It already has a wearable form-factor and it has RF for wireless communications, someone makes a heart rate monitor that syncs with it, but beyond that I'm not sure what you would do about data streaming or logging. It has a segmented display, not a pixel display so UI could be an issue too. You didn't say exactly what the device will do with the data, if it will be displayed in realtime, logged, transmitted, etc.