Nyquist theorem says that you have to sample at least 2x the frequency of the incoming signal to prevent aliasing. However, if you aren't just trying to avoid aliasing, but also want an accurate representation of the waveform, you must sample at MUCH higher than that. There isn't an equation for that, it just depends on the input signal and what shape it is. Usually for normal waveforms like sinusoidal, 10 times over sampling is recommended.
As for multiplexing, it depends on your board. For the one you have, yes, if you read 15 channels at 1000 S/s then the board is running at 15 kHz and channel 15 is read roughly 1 ms away in time fom channel 1. If you need simultaneous sampling, NI provides simultaneous sampling DAQ boards(6110E, 6111E) and a connector bl
ock to do simultaneous sample & hold (SC-2040).
As for recommending hardware, it sounds like you will need to go to two cards. NI doesn't have a faster MIO board that has 24 digital lines. You can get a 24 line DIO board (6503) really cheap though. Then for your MIO board, it will depend on if you need simultaneous sampling. The 6110E has simultaneous sampling and is really fast (5MS/s), so it would probably be best.
In the future, you should submit your questions like this to the Measurement Devices->Multifunction I/O section of Developer's Exchange instead, or call National Instruments so our sales representatives can help you with your hardware selection.
Best Regards,
Chris Matthews
Measurement Studio Support Manager