Being pressured to GOTO the dark-side
Solution 1:
How many bugs have been introduced because of incorrectly written GOTOs? How much money did they cost the company? Turn the issue into something concrete, rather than "this feels bad". Once you can get it recognized as a problem by the people in charge, turn it into a policy like, "no new GOTOs for anything except simplifying the exit logic for a function", or "no new GOTOs for any functions that don't have 100% unit test coverage". Over time, tighten the policies.
Solution 2:
GOTOs don't make good code spaghetti, there are a multitude of other factors involved. This linux mailing list discussion can help put a few things into perspective (comments from Linus Torvalds about the bigger picture of using gotos).
Trying to institute a "no goto policy" just for the sake of not having gotos will not achive anything in the long run, and will not make your code more maintainable. The changes will need to be more subtle and focus on increasing the overall quality of the code, think along the lines of using best practices for the platform/language, unit test coverage, static analysis etc.
Solution 3:
The reality of development is that despite all the flowery words about doing it the right way, most clients are more interested in doing it the fast way. The concept of a code base rapidly moving towards the point of imploding and the resulting fallout on their business is something that they cannot comprehend because that would mean having to think beyond today.
What you have is just one example. How you stand on this will dictate how you do development in the future. I think you have 4 options:
Accept the request and accept that you will always be doing this.
Accept the request, and immediately start looking for a new job.
Refuse to do and and be prepared to fight to fix the mess.
Resign.
Which option you choose is going to depend on how much you value your job and your self esteem.