Linear is better typically. The flow rate combined with fraction size and length of time gives you better resolution for which proteins are coming off the column at what point.
Once you've narrowed down the imidazole concentration at which your protein comes off the column, you can in future just stick to concentrations around that area, though it's still advisable to use gradients either side of that concentration as your preps are never likely to be completely consistent.
How do you know you're losing 80% of your protein before achieving purity? If your protein isn't separating from other contaminants during IMAC, you can try switching to an IMAC optimised strain (I use NEB BL21(DE3) NiCo21's).
Usually you'll have to do some downstream purification in any event. Gel filtration is common. You could also consider a different column chemistry such as anion exchange.