First HF Rig...
For what it's worth, my first setup was as follows:
IC-718
MFJ-4125 "MightyLite" 25A Switching Power Supply
LDG AT-7000 Tuner
VanGorden Multi-Band Dipole (*not* G5RV)
This is still my fixed-station setup, two years after getting my license.
IC-718 is easily moded for MARS/CAP, easily moded to do 200W ssb without frying the radio, can be computer-controlled with an additional $30 part and a free software download, and is small-enough to be used as an under-dash mobile, if necessary. It is a no-frills, tried-and-true radio with simple layout and solid functionality. True it is not an HF+6m rig like the IC746, but (even comparing new IC718 to used IC-746) it is still a better bargain, IMHO.
Drawbacks are that it does not have a remote head, so if you *did* want to move it between fixed and mobile, you'd have to mount the whole radio *somewhere*; also (as mentioned earlier) it is only HF 10m-160m stock (or continuous 150kHz-30MHz if moded)--unlike the IC746 (HF+6m) or the IC-706MkIIG (HF+6m+VHF+UHF).
In terms of antenna--first, definitely get a tuner. Indispensible.
Second, if you could only have *one* antenna, and the only concern is HF functionality....the longest, highest-placed dipole you can get is what I would use. I chose the VanGorden multiband dipole simply because it would cover all the bands that the IC-718 has with *one* antenna; it's easily erected, easily stowed, easy to stash, and didn't require anything additional other than a 4:1 balun and some rope.
Drawbacks...unless the dipole is high as hell (like 250 feet up), it's pretty much an NVIS (near-vertical incidence skywave) antenna on 80-160...if you can get it up 80 feet it's not quite NVIS on 40m, and if you can get it up at least 40 feet it's a *very* good performer on 20, WARC bands, and 10m. If you can spring for two of them and a coax switch, you can run one N-S, the other E-W, and pretty much have great coverage worldwide...but it's not a beam--therefore not directional; it doesn't have any gain, and (depending on the height of the antenna and the frequency being utilized) has little to no front-back or front-side isolation. It *will* get you on the air, cheaply, and fairly effectively. "How effectively?" --you ask? Washington DC to eastern Europe and Colorado to Japan at the bottom of the sunspot cycle with S-8 - S-9 reports on 20m, and strung as an inverted-vee, and not even a true dipole. What more could you ask for from a starter antenna?
Other people might be able to comment intelligently on Icom vs Kenwood vs Yaesu; both of my rigs (the IC-718 and my mobile rig, an IC-706MkIIG) are both Icoms, so I will save the brand wars for someone else.