I also walked into a mess. My predecessor was a dictatorial type of leader whose primary method of communication was to yell at people. She knew the only "correct" way to do everything, and she imposed her own will on people rather than involving them in developing solutions. The first three weeks I was on the job nobody came into my office, because they were used to only bad things happening in there. I set the tone early, telling the staff that if there was going to be any drama it would be of their own making, because it wasn't going to come from my office. My department had also been at war with pretty much every other department in the facility, because my predecessor approached other department heads the same way she did her own staff: We have a problem, and here is how you are going to fix it. She tried to force her own solution on them rather than with mutual respect and cooperation. I had to spend considerable time building relationships with other department heads, and assuring them that if we have problems of mutual interest, we will arrive at a solution that we both can live with.
Like you, I had staff with attendance and punctuality problems. Some had previously been dealt with severely, while others were pretty much allowed to do as they pleased. It took a while (and several letters of instruction) for people to get the idea that (a) I am paying attention to what they are and are not doing, and (b) everyone is going to get fair and equal treatment.
When you walk into a situation that has been poorly managed, it takes time, effort and a lot of frustration along the way to get it under control. However, if you are firm, fair and consistent you will be respected, and your staff will appreciate the change in atmosphere. Managers who are lax on things like evaluations usually don't pay attention to other, more important issues either. You can bet that your staff has recognized this, and many of them have probably developed the same lax attitudes toward what they are doing. Fixing this won't happen quickly, but it will happen. Just stick to the path you set.
While it is therapeutic to spell out everything you are dealing with in a forum like this amongst your peers, you will drive yourself nuts if you take a "whole picture" view of things as you proceed to create some semblance of order. Prioritize what you want to do. First and foremost, you need people on duty and properly doing their jobs to accomplish anything, so address the personnel issues first, particularly attendance issues and any performance problems. Once those are relatively stable, you can begin to look at any procedural changes you want to make. Once you start those, change one thing at a time and allow people time to adjust. People don't deal well with a lot of major changes made all at once. They need time to adapt to the new way of doing things. Engage your staff as you develop better ways of doing things. They will appreciate having input into changes in their tasks, and the buy-in is always better when solutions are mutually developed rather than imposed (not that there aren't occasions when you have to do this, too). Give them credit for their knowledge and skills. Soliciting their ideas and implementing the good ones is a good way to acknowledge their skills and expertise. Openly recognize those who make significant contributions.
Perhaps most importantly, leave your problems at the door when you go home. There aren't any problems that require your 24/7 attention, so give yourself time to unwind and not think about work.
Now past the six year mark in this job, things run pretty much smoothly, the problems I do have are usually relatively insignificant, and when we have an acute staffing issue people are generally willing to develop solutions on their own and present them to me for approval. I have no problem finding volunteers. We have peace with the other departments. Employees realize that they will be treated with respect, but also that there are set expectations.
The tone is set at the top. Good luck, Keep us posted on how things are progressing.