Rounding the edges of all the tiles is out of the question. Though, you might want to try to file down some of the worst offenders.
Ad hoc grout is likely to crack. At the very least, scarify the entire surface of the grout first.
Re-grouting it, it isn't going to be much different but it could be a little better. You don't have to get it all out, just make enough room for a solid bead to fit. Aim to achieve at least a 1/4" trough, and take what can you get. The deeper you go, the longer it will last.
See here, grout removers:
Tools and procedures for re-grouting a shower
Less than helpful comments:
Don't use 1/4" grout lines on cut stone tile.
Don't use 2" tile on a floor. Use true mosaic or normal sized tile.
No matter what you do (aside from installing different tile), I doubt it will ever be fun to stand on with bare feet. Slap some temporary grout over the existing and see if it's worth doing a full, meticulously attended, re-grout.