I have been told that Samsung seem to be a good choice and the the A04s will fit my budget.
I bought a Samsung SM-A310F (Galaxy A3 2016) outright, as my first "smart" phone, specifically because it is relatively small and had a decent camera (for its time). I find the size (and cost) of top-of-the-range smart phones outrageous, and even then the size is a compromise for using as a tablet... so I have a tablet for non-phone things! Nonetheless, it is occasionally handy that I can use the phone for email and messaging, web browsing, or the odd app.
The camera was the main point, the best camera is the one you have on you at the moment so the one built into something that's almost always on my person needed to be of decent quality and ability. It's good enough, but my iPad camera is better (and that's usually with me as well, and much more convenient to use for non-phone things), and modern phones would knock the spots off it (but again, multiple lenses seem ridiculous).
My A3 is sluggish by modern standards, but its main problem now is battery life. If you expect to buy for the long term, you should look for the (now rare) models with user-replaceable batteries. My A3 compromises on that to be as small as possible. A friend's A4 of similar era has a user-replaceable battery. I have replaced my battery (a complex procedure), but that doesn't seem to have helped and I suspect the (rip off?) replacement might not be kosher. With a user-replaceable part, the manufacturer supports replacement by making genuine parts available.
However, as the primary market for phones wouldn't be seen dead with a model more than two years old, the modern trend is for sealed-for-life units. But there is now a movement towards reducing waste, so this might change. I believe Nokia are now offering a unit with replaceable components, and there is a niche manufacturer been doing this for a while (but I suspect expensive through low volume).
The bottom line is this: decide what you REALLY want to use the phone for. If you only want it as a phone + "emergency" Internet, then there are much cheaper options than Samsung and if the phone is cheap enough perhaps it doesn't matter about the battery. If you want it as a mobile computing device, then budget constraints will compromise performance, and a small screen limits usability.
It comes with a USBC to USBC cable which would require an appropriate charger
Another trend is not to supply a charger with the phone, and this is to limit waste because surely everyone
has a USB wall wart don't they?
There is no need for you to use the supplied C-C (really?) cable for charging. A standard USB-C will do fine, with a standard USB wall wart, and the standard strategy is to charge the phone overnight. The complexity begins with fast charging (my A3 pre-dates fast charging), where the phone conducts a negotiation with the charger (or uses voltages on the data lines as ID) to boost the output voltage and thus transfer more energy to the phone without increasing the current (which would overheat the connectors). There is supposed to be a standard for this, but as usual Apple went its own way, so in general (for fast charging) you need an Apple-specific charger or a Samsung-specific charger (and a phone capable of fast charging). Even with a wall wart supplied by the manufacturer, don't just assume it is automatically a fast charger.
USB-C has much the same convenience as Lightning, ie it can be plugged in either way around. Compared with the fumbling I used to have with the micro-USB for my A3 (where it was not at all obvious which way around it should be), the Lightning on my iPad is simplicity itself. I solved all that by fitting 4-way magnetic adapters EVERYWHERE, which also provide swivels, so now every device I have which needs regular or occasional charging simply snaps magnetically to one of my universal charge points (including in the car), and the swivel removes the usual point-of-failure where the connector comes under bending strain (and if the strain is too great the magnetic coupling acts as a mechanical fuse and simply disconnects). 2-way magnetic adapters are also available, but these would not support data transfer if it were needed. The magnetic couplers also prevent dirt ingress (being permanently installed), and eliminate contact wear.