Playing around at the online etymology dictionary, it appears dismiss is the oldest—early 15th century. Sack and fire are from the 19th century, and laid off in this sense isn’t until the 1960s. Terminate, as in dismiss from a job, is first attested in 1973.
