To start with, forget the math of the gear calculators. You can use those later....
If you are spinning out - is you cadence at 90-100 when spun out? If not, leave the chain rings and work on spinning technique. Changing the chain rings will help only for the times you are spinning out. If you spinning out for a only a short percentage of the time, it may be best to accept it and use the time to perfect spinning fast and smooth. Keep in mind an increase the size of the chain ring comes at the cost of larger speed jumps between gears.
If you are finding the jumps between gears are too large (i.e. can't get the right gear for the speed so 'hunt' for a comfortable gear), reducing the size of the largest cog will reduce the size of jumps between the larger cogs- exactly how far it goes depends on the specific cog sizes used in the cassettes. Ideally you want a cassette size that gives you the lowest gear you use on its largest cog.
Head out on ride that represents a high speed day you regularly have (e.g. a tail wind on a long down hill), pay attention to the high speed sections - how much are you spinning out and how much would you benefit by going 5% faster (36->38 is about 5%) keeping in mind that 5% faster needs much more than 5% effort.
Now focus on your slow speed - e.g. hill climb into a head wind - what is the lowest gear are you using? Select a cassette with the largest cog the same size as the lowest gear you you want. You may want to have a bit larger so you have another gear or two spare.
If you think you will increase the chain rings as well as change cassette, you may want a bit lower again (26->28 is about 8%), this is where you may want to reach for the gear inch calculators discussed in other questions..
Overall the cost of dumping a good cassette and chain rings for 2 tooth differences is likely to be disappointing, but if replacing due wear, certainly worth while.