We can't possibly give you an estimate:

There will be work to your main panel as well as probably fees from the power company to do this. Labor costs are highly variable around the country.

Get estimates, get references.

1: 1955 slab-foundation house originally supplied with 3-phase, but then the more common 240 single phase. The original 3-phase equipment was still in use. Main panel and outside main disconnect outside near meter pan. Two indoor fuse (sub) panels and another (sub) fuse panel/shutoff by the AC compressor. I don’t really know how many amp service it was, but the wires in the drop were smaller than the new one.

2: Same house obviously. New mast, meter pan, 200 amp service panel in essentially the same place outdoors. The original cables to the indoor panels were cut in the attic and spliced in two large boxes to reroute to the new service panel. There were 19 old circuits. The electrician ran 12 new functioning circuits including a three-way light on the back porch. At least half of these were to the opposite end of the house to the kitchen and porch. There were 4 spares that terminated in the attic junction boxes for my future use.

As ronnatalie pointed out, it is really impossible to say how much your job will cost without knowing a lot of details like how the walls are constructed in your house, how accessible the basement and attic are,….. Mine involved a lot of unpleasant attic work and the new cables in the exterior walls was mostly fished by cutting holes in the eaves to access the top.

In Virginia the POCO is responsible for everything up to the meter base, and used to give even those away for free since they had a 'preferred' one.

Updating the overhead lines was on their nickel also if you increase your panel capacity.
Remember that the overhead wires are also not under the NEC since they are POCO distribution wiring.

It is pretty common to place a new meter base beside the old run, hook the new base to the main panel, and then use jumpers from the old base on the bottom to the top of te new base.
Shorting bars on the new base bypass it, and with the meter plugged back into the old base the power was up and running in a single day.
After a final inspection, the POCO gets around to unpdating the feed to the new mater base and moving the meter over.

In other places the homeowner is responsible for everything from the weather head down (mast if required), and the POCO may be required to cut the feed and then reconnect it when the work is completed and inspected. That can leave you without power for a day or two.

Some places will not allow upgrades if the main panel is still fusses.
A new breaker panel is then required, and depending on how 'messy' the old work is it can take a lot of work to update the panel.

How do you know that the existing drop location is good and meets all current clearances?

What if a mast is required, how about a roof patch where the mast goes through the roof?

The list goes on and on...

Even stating it "shouldn't be more than $3500.00" could be way off base.

To the OP - follow the original advice and get an estimate from a couple local electricians, that is the only way to get a real estimate of what the job will cost.

It's very rare for unions to get residential work (such as houses, large condos are different). Where are union electricians raising prices of home service upgrades?

As mentioned, prices vary GREATLY by area. Not only cost of living, but requirements as well. Someone above mentioned that the POCO is responsible up to the meter pan. Around here the POCO only goes to the overhead splice, the homeowner has to pay for the pipe or rope.

Yeah, and many times it is hack work in a home because they have no idea what they are doing in a home. Give them pipe and wire and they will usually do great work. Give them NM and plastic boxes and SE cable and residential codes and they flounder.

"Around here you can expect to pay a licensed EC about $4-5K while a unlicensed union electrician (still a "pro", just not having a contractors license) will charge about $2K. It's a big difference not having to pay for a shop, trucks, insurance, workman's comp, benefits, unemployment, stock, taxes, and everything else an EC has to pay."

Exactly. And in most cases this unlicensed and uninsured side work is illegal in many areas. If it is not technically illegal it IS undercutting legitimate contractors trying to make a living.
YET....the union will try to get the workers from any and every contractor to sign up. At the same time their policies forbid side work. This policy is conveniently ignored when the work they are stealing is from non-union "residential contractors" and not their own.
This is because if a union contractor had to compete with a legitimate open shop electrical contractor for residential service upgrades they're price would be way out of line.
The BA needs a new Cadillac you know.

These union side-job guys are NO better than Joe's Handyman Service offering to do a 200A upgrade for half as much as a LEGITIMATE contractor.

It's funny how you say:
"If it is not technically illegal it IS undercutting legitimate contractors trying to make a living."
and complain about the union guy undercutting the EC, yet you have no problem with the non union guy undercutting the union guys:
"This is because if a union contractor had to compete with a legitimate open shop electrical contractor for residential service upgrades they're price would be way out of line."

Nevermind the fact that you generalized ALL union electricians to be no better than "Joe the Handyman". Do you do the same stereotyping with races and religions??

I'm not a union member, but I just don't have such a huge hatred for 75 million fellow Americans.

Hopefully something more affordable can be found by calling electricians directly. I'll start with Angie's List.

P.S. my existing panel is a reasonably-modern "Square-D" mounted on the outside of the house right under the meter. It is fed with conduit, which I would guess should make it easier to work with than an internal NMB-fed box.

But I agree with you, if all your doing is changing the service, why would you want a GC in the middle.