Thanks to everyone who contributed their 2 cents on this post. Just figured I'd circle back here and let people know how it went. I had a second electrician come and give me an estimate that was in line with what I had read in other threads. To save a little money I did do some of the manual labor myself. I sunk a 6x6 post at the top of my driveway, concreted it in, and trenched about 75% of the 40 or so total feet from the post to my house. I dug the trench by hand with a trench shovel. For the area that was grass, I dug down an inch or two and then gently "flipped" the grass over, leaving the grass connected on one side before digging down further. I think this turned out to be a good idea because after they filled in the trench they just flipped the grass back over, minimizing the impact to my yard. I spent probably $100 between the shovel and the materials for the post and he charged me $1100 for the work. Much better than 4k.
Now if only I could get them to deliver me my MYP. It's hard staring at that beautiful charger and not having a car for it yet!