In the past couple of years I've used Firefox on a 600Mhz mobile Celeron with <512MB RAM (my EeePC).
Firefox and Chrome are the best for security updates. You can install the browser from their websites and receive automatic updates. Or just install & update them through your Linux distribution. Other browsers may not have as good security support.
If you use Debian Linux, they recommend their versions of Firefox or Chrome. Other browsers "built upon the webkit, qtwebkit and khtml engines are included in Debian 7.0, but not covered by security support. These browsers should not be used against untrusted websites" i.e. they're not safe to use on Debian.
Towards the end, I got frustrated with Firefox on the EeePC. One busy tab would stall the whole browser. Especially frustrating when the reason you use multiple tabs is because pages are slow to load! (An old habit from dialup days).
Debian would give you the oldest version of Firefox (ESR 10). However I personally can't resist the newer versions. Remember that the big push at Firefox now is running it on mobile phones, so new versions improve efficiency in various ways. 4.0 was a retrograde step in terms of demands on the hardware. Therefore I'm not confident that ESR 10 is good to stick in that regard :(. It might be better to try ESR 17 from the Firefox website. ESR means less frequent feature updates, so perhaps less worrying about performance regressions when Firefox is updated.
I didn't notice problems with the EeePC's limited RAM. Firefox can have a slight advantage for memory consumption, due to not using multiple processes. However you can (and should :) upgrade RAM on old computers without too much difficulty. 512M of RAM is a minimum requirement for browsing the web. I tried simulating a Raspberry PI model with less RAM and no swap, and the browsers kept running out of memory and dying.
What you would lose by forsaking Firefox is some of your desired features. Bookmark tagging seems to be Firefox-only. And Firefox has the best addons.
incremental search? Search google.com, for instance, for XY, and then all links google displays, and then all links the links link to? b) Which ohter browser did you already look at? Chrome, opera?
Ctrl + f. By incremental link search I mean something like possible for example in luakit
ctrl-fsearches the active page. How is that incremental?