It seems that panzaman has jumped into the thread without actually looking at your issues
What you have here has nothing to do with lag in the common sense of the word. Especially at these forums, people refer to lag as the delay between action and visualisation, that is, slow drawing of some sort.
Your first issue is with new Mail. I also have it. The reason why it takes so long for the inbox to show the correct number of emails is the synchronisation mechanism Mail uses. When you delete something, it has to perform a round trip to the server, tell the server to delete the message and then update the counts accordingly. However, the server plays a key role here, as it is actually the agent that performs the deletion. With my mail, deleting a single message is fast and updates fast. But when I delete a bunch of messages quickly, then it starts to act up. I believe the reason is that its waiting for the server to perform the operations. The deletion is not instantaneous and the server will throttle the responses if it receives lots of requests within short time. In another words, Mail is just being honest here and waits until the messages are actually deleted. Which is not what a user wants. One way to "fix it" is basically to "lie" to the user — for example, report that the messages are deleted, while they are actually not. I hope Apple will implement it in the future. They did say that Mail was a complete rewrite, so some rough edges should be expected — no first version is ever perfect.
Your Safari problem is a different one and it almost looks as if it has some problems with accessing the history. I do not have this issue nor does any other machine in my care (I maintain around a dozen Yosemite machines and none of them has this kind of issue). Did you try running repair permissions?
