I have been through the process of successfully filing and completing a patent (more than one actually) as a very small company and even a single person at the start. I would agree with the comment about how useful they are for small companies. I could drone on about stats, but the short of it is that 1 out of 100 patents will ever be picked to go to court on contingency (where you do not have to pay the fees). Otherwise it is, on average, 2 million to get to court against a foe. The flip side is it costs the opponent hundreds of thousands to fight even going to court. I would not do it unless your plan is to simply license it out and that is the primary business plan as opposed to bringing it to market. You will not be able to fight a company with deep pockets with a patent unless you have a firm that is essentially your partner. In other words, while I think it is worth having patent protection, it is not something you should think provides much unless you succeed in the market.
Second, if you do it - ignore anyone that states you should do it yourself. The short of it is this - you will write a worthless patent. The claims will be malformed and even something as simple as the description can be destroyed by choosing one word over the other. With technology, I would make an attempt and then take it to a lawyer to proof to save money. The Nolo book is okay and there are others, by Aspen publishing that will help. I would expect to spend up to 20k... keeping in mind every rejection will cost you more money (you will likely get rejected at least once). Every step has fees in addition to the lawyer fee. I would highly recommend Software Patents and Drafting Patent Licensing Agreements from Aspen publishing as a start. The Nolo book is okay, but even if you ask the author (which I have) about the specifics with tech, it is only cursory. Even if you think you can pick up things such as the wording, it is highly unlikely unless you want to put in a lot of time... there is a very specific language to it.
Per licensing, I would recommend the book above. Specifically regarding your question - sure you can license your tech before it is patented (granted), but if they are infringing you cannot compel anyone to until it is granted. In other words, it is good to file the patent before you are seeking people to license your product, but you cannot have any teeth until you do.
Choosing a patent lawyer is somewhat tough. I would start looking at the patent list of firms. I do not have the link handy, but Google it. Every year there is a list of the top 100 or 500 firms listed by patents granted. *One thing to keep in mind though before you go into detail, if you have any for certain competitors, I would ask them up front if they have a conflict of interest with any of them.
One thing that REALLY concerned me is this. You stated that you implemented something a few years ago. If this is true you may no longer be able to get a patent on it... or file it. You MUST file either a patent application - provisional or otherwise - within a year of anyone knowing about it. Thus, if you created something and people knew about it more than a year (people outside of the inventors), you are not able to get patent protection. That is a hard line law. As the post above stated, filing a provisional gives you an extra year BUT you have to file something within a year of it being public otherwise it is over.
As of type, yes, always choose methods if possibe and if you have code, it is recommended to file with that. Anything that strengthens your case.
Finally, while you may think it is easy to just get a patent, it is not. The average time it takes to get through the process is years.... It takes over 2 years just to have the intial viewing of it and then it goes from there. Many average ones take 5 years to go through. In that same vein, while many like to point out how there are many silly ones, it is not entirely true in this sense. What seems obvious as an overall concept may not be when you get down to the nitty gritty with the actual method of how it is done. Further, if you do end up sneeking one through that is silly, it will be worthless and you will have done nothing but waste your time and money. Unless you are the 1 person that gets a company to back you, likely for other reasons.
I would be happy to answer anything more. Sadly, for small businesses or micro sized startups, there seems to be very little real info that leads to a lot of wasted time and money.