Yes, most microcontrollers have enough hardware support so that threading is possible. If the hardware call/return mechanism is stack based, then all you really need is arbitrary access to the stack.
I've done multi-tasking many times on various PICs and dsPICs. Everything from the PIC 18 on up support true threading. The 14 and 12 bit core parts don't give you full access to the call stack, so you can't do real threading. I've done what I call pseudo-threading on those a few times. You can still have something that mostly looks like a independent thread to the software, although there are restrictions.
In general, it's a useful software abstraction to handle any stateful asynchronous input with a separate task. I do this routinely, for example, for processing the UART command stream from the host.
Don't fall for the "super-loop" architecture, except for handling a number of individual events. It then really becomes a event loop, so it's better to call it that. I usually have the original task run the event loop, after initializing the system and starting whatever other tasks that are needed.
Also don't make the mistake of assuming that multi-tasking means preemption, or that it requires a RTOS. I've done well over 100 microcontroller projects, and have used multi-tasking many times. I have so far not found a case where preemptive multi-tasking or a RTOS would have made sense. If you find yourself wanting such software structure, then you're probably not really doing micro-controlling and are closer to general computing, even if it is embedded.
Basically, use a separate task whenever you would otherwise want to use a state machine called periodically from a blooper-loop. The code is much cleaner, easier to write, and easier to maintain when the PC is the state variable. Just make sure to call TASK_YIELD in any loop where you wait for a event.
Since the main event loop is its own separate task, it also calls TASK_YIELD periodically. I usually put the call to TASK_YIELD at the start of the main event loop. It then checks each event in sequence. When it finds a triggered event, it handles it, then jumps back to the start of the loop.
My multi-tasking code for PICs is available for free in the PIC Development Tools release at http://www.embedinc.com/pic/dload.htm. Look at files with "task" in their name in the SOURCE > PIC directory for the 8 bit parts, and SOURCE > DSPIC for the 16 bit parts. I have used these facilities extensively, so I think they are quite solid.
On a PIC 18, the call stack is in dedicated memory. TASK_YIELD therefore swaps out the used portion of the call stack to/from a save area for each task. On the 16 bit PICs, the stack is just W15 pointing to somewhere in main memory. That makes swapping tasks easier. Each task gets a stack area up front. Swapping tasks is pushing the registers on the stack, pointing W15 to the stack for the new task, and popping the registers off the stack.
I recently measured the task loop time on a current dsPIC33EP project. The processor is running at its maximum speed of 70 MHz instruction clock. In this case, there were 4 tasks. These were to process the UART stream from another micro, low level CAN frame receiving, higher level CAN frame processing, and the main event loop. When nothing was going on, the time for one full cycle thru all tasks was 7 µs.
To address your particular example, the periodic A/D readings should be taken in a interrupt routine. The SMS process should be a separate task, perhaps two. I'm not familiar enough with SMS to know whether receiving is really asynchronous to sending.
If so, use one task to handle whatever comes in whenever it comes it, and another task to send SMS messages, with whatever waiting on events that may include. When the SMS sending tasks waits on events, it calls TASK_YIELD in the loop, allowing all other tasks to continue while this task is stalled. If you're waiting on SMS responses, then have the SMS receiving task set flags whenever particular responses are received. The SMS sending tasks then waits on those flags, as appropriate.
This can all be handled very nicely with cooperative multi-tasking. A RTOS and all the baggage that comes with it would get in the way more than it would help.