iMessage is Apple’s proprietary messaging service between Apple IDs (blue bubbles). Your mobile service provider has no part in that. It wouldn’t require a new phone, unless the phone wasn’t properly reset before you set it up as your own. Apple Store staff would have told you that.
iMessage uses the Messages app, which also supports SMS text messages, a messaging service between phone numbers. Your mobile service provider would be involved in that, as it requires cellular connectivity. I can’t see how that would involve upgrading to a higher plan.
iMessage requires a valid Apple ID. You can use a previously created Apple ID (preferable if you have that), or set up a new one on the to-be-configured Apple device.
Messages support - Official Apple Support
If you are using a pre-owned iPhone, then make sure that it is fully detached from the previous owner’s account and Apple services and phone number, and that it has been correctly reset and set up again “as new”. Part of that may have to be done by the previous owner: What to do before you sell, give away, or trade in your iPhone or iPad - Apple Support.
A not-correctly reset device is one of the common issues with second-hand Apple devices.
A correctly reset iPhone, would present you with the “ℋℯ𝓁𝓁ℴ” screen, beginning with the question for setup language. If you haven’t seen that on these iPhones, then it was not done correctly.