for starters on a low budget, one can consider a 2nd hand Nikon D5100 or D5200. The latest is a D5300. Try not to get the LOWEST end IMO because you might outgrow their limitations. If your budget allows, a Nikon D7000/D7100 might be better because it higher end.
For Canon,600D, 650D, 700D are all decent cameras for beginners.
For m4/3 formats, Olympus has proved that smaller sensors dun mean lousier IQ. Check out the IP of their OMD-EM1 and EM5. Focusing speed has definitely improved. I am using EP3 which is supposed to be an older model, the focusing speed is pretty decent. Panasonic GX7 is pretty decent in terms of styling, handling, focusing speed etc.
Sony NEX are actually not bad, if one can live with the more limited choices of lens but good enough for general use.
BTW, EOS M is good for those who want to train their patience as it has one of the slowest auto-focusing speed EVER even in decent lightings.