Fused:
What is the smallest, most suitable Arduino board I could use
Look for a Pro Mini or a Mini (yes they're different).
moving bike? Would the data collected by the accelerometer be stored in the Arduino memory or are there accelerometers with their own memory onboard?
Neither. The Arduino has 2 kB of RAM, an accelerometer usually just enough for the current reading. For any form of logging of data you need external memory, like an SD card.