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.
EDIT
Typically I wouldn't expect that you would need to mess with pH very much when performing IMAC. I certainly have never had to. You are likely to need physiological pH to ensure native folding of your protein.
You can however use other additives if your protein is recalcitrant. For example, I often add 1mM DTT and 2M urea to my samples and then heat them slightly as my protein binds things easily and is extremely stable. GE Provide a whole booklet of supported additives for their columns, you may have the same thing for yours too.