Web services in NAV 2009 can call either CodeUnit or Page objects. Pages allow you to create, read, update and delete rows from their source table. CodeUnits offer greater flexibility, allowing you to invoke any action you can implement in C/AL. I think CodeUnit trigger arguements are limited to primitive types and Records.
NAV web services use Windows Authentication, so your linux app will have to be able to present Windows credentials accordingly. I'm not an expert in this area, so I'm not sure how difficult this is from a Linux machine.
With regard to the supported load, I would ask in the forum at mibuso - this is the largest community of experienced users I am aware of. I expect you will be limited by the CPU and memory of the web service host. NAV does not support clustering\load balancing on the web service tier, but I beleive it is possible to run several side by side.