There is a bit of a misunderstanding as to what happened here
Should I have told the new controller I was restricted at or above
4,500 even though the previous controller didn't explicitly say I was
restricted (recall she just said, "you can descend to 4500, if you
You were not restricted to anything (assuming you were within any airspace limitations), flight following is not the same thing as being vectored. Sometimes on flight following you will hear something like
VFR Altitude At Your Discretion
When you are on flight following you are subject to ATC vectors when they are issued in controlled airspace (A,B,C,D and E) but you are also free to maneuver within the VFR regulations so long as you are not asked to hold a course or avoid a certain area or move for traffic etc.
you can descend to 4500, if you want
This was not an explicit instruction and not one you needed to comply with nor the floor to which you could come down to technically. They were saying there was no apparent traffic conflicts and if you (for what ever reason) wanted to come down you were clear to at least 4500 ft.
However there are some cases under flight following where you should comply with instructions. Im actually not sure what the legality is on this since you technically don't need to take FF in which case "see ad avoid" is your responsibility. But on any note I have received something like
Turn left 20 degrees for traffic climbing out of 2500 for 8000
In my experience flying trainer sized stuff in the congested north east corridor, flight following (which ultimate often comes from approach control in this area) will vector you out of the way for jet traffic. Strictly speaking this has occurred in class E airspace where VFR aircraft are largely free to do as they wish.
You may have also been handed off to an angry controller, but you should stick to VFR cruising altitudes when possible as per § 91.159.