Welcome to the boards, good to have you with us! I myself grew bored of playing W40k and just go for Epic these days - it is a fantastic game and I'm sure you'll love it. I'll try and help with some of your questions and talk about what I do for my own armies.
Personally I base with a mix of the same sort of gravely stuff I might use for 28mm, but also with finer sand mixed in. I found some really fine sand on a local beach and collected a big tub. It's nice to have some bigger bits in the mix, but finer material is good too I find, as otherwise the feet of the epic figures can get buried under the basing material. Some of the bases in the army you ask about also have some of the plastic ruins used on them, sadly these are no longer available, but you could probably find some on ebay or trade some from people. I think that's just normal static grass, just applied sparingly than, not certain though. I use some static grass, along sometimes with some of the older flock type which is made up of tiny little dots.
Infantry come on 12x40mm bases, the older type of bases were 40x40mm ones. Shining Spears are on bases originally used in the Warmaster game, which are 40x20mm. Vehicles tend not to be supplied with bases and it is up to personal preference whether individuals base them or not. Personally I like to and have bought a couple of hundred bases, which I'm working through basing all my vehicles on now, mostly using Warmaster bases. For some where the vehicle is small, such as a Rhino, I cut a certain amount of the length off the base. Some people base things like Dreadnaughts, Land Speeders, Vypers, ect on the older 40mm square bases, but personally I prefer to go for round ones and certain of my armies will be based entirely on round bases for aesthetic reasons (the epic basing rules are very flexible compared to GW's other games and allow for this). I used to use 1p and 2p UK coins, but these days have switched to using the 'Battle of Five Armies bases' from the rare but still sold GW game, which are 25mm round like the W40k ones, but also usefully the same height as the Warmaster ones (some people do just use W40k bases but I think for epic scale models these look poor raised up so much) which can be ordered from the bases section of the GW webstore.  For some larger vehicles like my Land Raiders I glued two Warmaster bases together (glued to each other and the vehicle these seem pretty sturdy). For other large vehicles / units / armies where appropriate I use W40k round bases (cut and filed down to the same height as the other bases because I'm a bit obsessive with this) e.g. for my Vultures. Some of these I could maybe just buy plasticard of the appropriate thickness and cut them myself, but I don't trust my ability to cut them precisely and cleanly enough, so prefer to buy them in. A photo here of my some of epic illustrates a lot of this:
Old titans used to come with bases with rotatable card bits in them to displays it's number of shields. Personally I like to keep all my bases the same height and so prefer the thin 60mm round bases they sell these days and which may or may not come with Titan models you buy. If not they can be ordered from GW again, they're called Titan Bases (and are 60mm round rather than 80mm you mention, I'm certain there isn't an 80mm base)
Spent longer writing that than I intended (quiet / lazy day at work) but I hope that helps.
Best, Glyn
Glad to be of help. The BOFA bases are still available. I tried linking directly to the page but it seem to want to work, from the Australian online store you want to click on the hobby tab and then select bases on the left and they're on that page - "25mm Round Battle of Five Armies Bases".