I'm glad you found improvement with a new app, but it's not going to be a viable solution, as any 'zoom' you do on a smartphone (other than a phone with a dedicated zoom lens like the iPhone X) is an optical zoom, so it's just taking the photo and cropping in in order to zoom, so you're going to get the grain.
As for a phone designed to take good photographs at a reasonable price, the Google Pixel 3a is that phone, it's Google's "budget" phone with the best camera on a smartphone.